Submission #3466456
Source Code Expand
#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<cstring>
#include<string>
#include <math.h>
#include<algorithm>
// #include <boost/multiprecision/cpp_int.hpp>
#include<functional>
#define int long long
#define inf 1000000007
#define pa pair<int,int>
#define ll long long
#define pal pair<double,pa>
#define ppa pair<int,int>
#define ppap pair<int,pa>
#define ssa pair<string,int>
#define mp make_pair
#define pb push_back
#define EPS (1e-12)
#define equals(a,b) (fabs((a)-(b))<EPS)
#define VI vector<int>
using namespace std;
class pas{
public:
int x,y;
pas(int x=0,int y=0):x(x),y(y) {}
pas operator + (pas p) {return pas(x+p.x,y+p.y);}
pas operator - (pas p) {return pas(x-p.x,y-p.y);}
pas operator * (int a) {return pas(x*a,y*a);}
pas operator / (int a) {return pas(x/a,y/a);}
// double absv() {return sqrt(norm());}
int norm() {return x*x+y*y;}
bool operator < (const pas &p) const{
return x != p.x ? x<p.x: y<p.y;
}
// bool operator < (const pas &p) const{
// return y != p.y ? y<p.y: x<p.x;
// }
bool operator == (const pas &p) const{
return x==p.x && y==p.y;
}
};
class Point{
public:
double x,y;
Point(double x=0,double y=0):x(x),y(y) {}
Point operator + (Point p) {return Point(x+p.x,y+p.y);}
Point operator - (Point p) {return Point(x-p.x,y-p.y);}
Point operator * (double a) {return Point(x*a,y*a);}
Point operator / (double a) {return Point(x/a,y/a);}
double absv() {return sqrt(norm());}
double norm() {return x*x+y*y;}
bool operator < (const Point &p) const{
return x != p.x ? x<p.x: y<p.y;
}
bool operator == (const Point &p) const{
return fabs(x-p.x)<EPS && fabs(y-p.y)<EPS;
}
};
typedef Point Vector;
#define pl pair<int,pas>
struct Segment{
Point p1,p2;
};
struct star{
Segment se[5];
};
double dot(Vector a,Vector b){
return a.x*b.x+a.y*b.y;
}
double cross(Vector a,Vector b){
return a.x*b.y-a.y*b.x;
}
bool parareru(Point a,Point b,Point c,Point d){
// if(abs(cross(a-b,d-c))<EPS)cout<<"dd "<<cross(a-b,d-c)<<endl;
return abs(cross(a-b,d-c))<EPS;
}
double distance_ls_p(Point a, Point b, Point c) {
if ( dot(b-a, c-a) < EPS ) return (c-a).absv();
if ( dot(a-b, c-b) < EPS ) return (c-b).absv();
return abs(cross(b-a, c-a)) / (b-a).absv();
}
bool is_intersected_ls(Segment a,Segment b) {
if(a.p1==b.p1||a.p2==b.p1||a.p1==b.p2||a.p2==b.p2) return false;
if(parareru((a.p2),(a.p1),(b.p1),(b.p2))&¶reru((a.p2),(a.p1),(b.p1),(b.p1))){
// cout<<"sss"<<endl;
if(dot(a.p1-b.p1,a.p1-b.p2)<EPS) return true;
if(dot(a.p2-b.p1,a.p2-b.p2)<EPS) return true;
if(dot(a.p1-b.p1,a.p2-b.p1)<EPS) return true;
if(dot(a.p1-b.p2,a.p2-b.p2)<EPS) return true;
return false;
}
else return ( cross(a.p2-a.p1, b.p1-a.p1) * cross(a.p2-a.p1, b.p2-a.p1) < EPS ) && ( cross(b.p2-b.p1, a.p1-b.p1) * cross(b.p2-b.p1, a.p2-b.p1) < EPS );
}
double segment_len(Segment a){
return (a.p1-a.p2).absv();
}
double segment_dis(Segment a,Segment b){
if(is_intersected_ls(a,b))return 0;
double r=distance_ls_p(a.p1, a.p2, b.p1);
r=min(r,distance_ls_p(a.p1, a.p2, b.p2));
r=min(r,distance_ls_p(b.p1, b.p2, a.p2));
r=min(r,distance_ls_p(b.p1, b.p2, a.p1));
return r;
}
Point intersection_ls(Segment a, Segment b) {
Point ba = b.p2-b.p1;
double d1 = abs(cross(ba, a.p1-b.p1));
double d2 = abs(cross(ba, a.p2-b.p1));
double t = d1 / (d1 + d2);
return a.p1 + (a.p2-a.p1) * t;
}
pair<Point,Point> circle_intersection(Point c1,double r1,Point c2,double r2){
double d=(c1-c2).absv();
double h=(r1*r1-r2*r2+d*d)/2.0/d;
double l=sqrt(r1*r1-h*h);
// cout<<d<<" "<<h<<" "<<l<<endl;
Point asi=c1+(c2-c1)*h/((c2-c1).absv());
Vector r1r2=(c2-c1)/((c2-c1).absv());
Vector sui={r1r2.y,-r1r2.x};
// cout<<sui.x<<" "<<sui.y<<endl;
pair<Point,Point> z=mp(asi+sui*l,asi-sui*l);
if(z.first.x>z.second.x) swap(z.first,z.second);
return z;
}
double dist(star s1,star s2){
double ans=10000000000.0;
for(int i=0;i<5;i++)for(int j=0;j<5;j++){
if( is_intersected_ls(s1.se[i],s2.se[j])) {
// cout<<s1.se[i].p1.x<<" "<<s1.se[i].p1.y<<endl;
// cout<<s1.se[i].p2.x<<" "<<s1.se[i].p2.y<<endl;
// cout<<s2.se[j].p1.x<<" "<<s2.se[j].p1.y<<endl;
// cout<<s2.se[j].p2.x<<" "<<s2.se[j].p2.y<<endl;
return 0.0;
}
ans=min(ans,segment_dis(s1.se[i],s2.se[j]));
// cout<<" "<<i<<" "<<j<<" "<<segment_dis(s1.se[i],s2.se[j])<<endl;
}
return ans;
}
int gcd(int x,int y){
if(x<y) return gcd(y,x);
if(x==y) return x;
if(x%y==0) return y;
return gcd(y,x%y);
}
class pa2{
public:
int x,y;
pa2(int x=0,int y=0):x(x),y(y) {}
pa2 operator + (pa2 p) {return pa2(x+p.x,y+p.y);}
pa2 operator - (pa2 p) {return pa2(x-p.x,y-p.y);}
bool operator < (const pa2 &p) const{
return x != p.x ? x<p.x: y<p.y;
}
bool operator > (const pa2 &p) const{
return x != p.x ? x>p.x: y>p.y;
}
bool operator == (const pa2 &p) const{
return abs(x-p.x)==0 && abs(y-p.y)==0;
}
bool operator != (const pa2 &p) const{
return !(abs(x-p.x)==0 && abs(y-p.y)==0);
}
};
string s[110];
vector<pa> ve1[110],ve2[110];
vector<int> zero;
pa ch(string st){
int r=0;
int mi=0;
for(auto c:st){
if(c=='(')r++;
else r--;
mi=min(mi,r);
}
return mp(r,mi);
}
pa ch2(string st){
int r=0;
int mi=0;
for(auto c:st){
if(c==')')r++;
else r--;
mi=min(mi,r);
}
return mp(r,mi);
}
vector<int> ans1,ans2;
signed main(){
int n;
cin>>n;
int allb=0;
int r1=0,r2=0;
for(int i=0;i<n;i++){
cin>>s[i];
pa r=ch(s[i]);
allb+=r.first;
// cout<<r.first<<" "<<r.second<<endl;
if(r.first==0) zero.pb(i);
else if(r.first>0){
ve1[-r.second].pb(mp(r.first,i));
r1++;
}
else{
string t=s[i];
reverse(t.begin(),t.end());
r=ch2(t);
// cout<<" "<<r.first<<" "<<r.second<<endl;
r2++;
ve2[-r.second].pb(mp(r.first,i));
}
}
if(allb !=0) {
cout<<"No"<<endl;
return 0;
}
for(int i=0;i<110;i++){
sort(ve1[i].begin(),ve1[i].end());
sort(ve2[i].begin(),ve2[i].end());
}
int ima=0;
for(int cnt=0;cnt<r1;cnt++){
int k=ima;
if(k>=110) k=109;
while(ve1[k].size()==0){
k--;
if(k<0){
cout<<"No"<<endl;
return 0;
}
}
ans1.pb(ve1[k].back().second);
ima+=ve1[k].back().first;
ve1[k].pop_back();
}
ima=0;
for(int cnt=0;cnt<r2;cnt++){
int k=ima;
if(k>=110) k=109;
while(ve2[k].size()==0){
k--;
if(k<0){
cout<<"No"<<endl;
return 0;
}
}
ans2.pb(ve2[k].back().second);
ima+=ve2[k].back().first;
ve2[k].pop_back();
}
string ans="";
for(auto v:ans1)ans+=s[v];
for(auto v:zero)ans+=s[v];
for(int i=r2-1;i>=0;i--)ans+=s[ans2[i]];
// cout<<ans<<endl;
pa z=ch(ans);
if(z.first==0 && z.second==0)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Parentheses |
User |
smiken |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
12682 Byte |
Status |
AC |
Exec Time |
3 ms |
Memory |
256 KB |
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample_00, 00_sample_01, 01_minimal_00, 01_minimal_01, 01_minimal_02, 01_minimal_03, 10_detarame_00, 10_detarame_01, 10_detarame_02, 10_detarame_03, 10_detarame_04, 10_detarame_05, 10_detarame_06, 10_detarame_07, 10_detarame_08, 10_detarame_09, 20_tyotto_kasikoi_00, 20_tyotto_kasikoi_01, 20_tyotto_kasikoi_02, 20_tyotto_kasikoi_03, 20_tyotto_kasikoi_04, 20_tyotto_kasikoi_05, 20_tyotto_kasikoi_06, 20_tyotto_kasikoi_07, 20_tyotto_kasikoi_08, 20_tyotto_kasikoi_09, 20_tyotto_kasikoi_10, 20_tyotto_kasikoi_11, 20_tyotto_kasikoi_12, 20_tyotto_kasikoi_13, 20_tyotto_kasikoi_14, 20_tyotto_kasikoi_15, 20_tyotto_kasikoi_16, 20_tyotto_kasikoi_17, 20_tyotto_kasikoi_18, 20_tyotto_kasikoi_19, 30_ookii_00, 30_ookii_01, 30_ookii_02, 90_teuchi_00, 90_teuchi_01, 91_challenge_00, 91_challenge_01, 91_challenge_02, 91_challenge_03, 91_challenge_04, 91_challenge_05, d_00_sample_00, d_00_sample_01, d_01_minimal_00, d_01_minimal_01, d_01_minimal_02, d_01_minimal_03, d_10_detarame_00, d_10_detarame_01, d_10_detarame_02, d_10_detarame_03, d_10_detarame_04, d_10_detarame_05, d_10_detarame_06, d_10_detarame_07, d_10_detarame_08, d_10_detarame_09, d_20_tyotto_kasikoi_00, d_20_tyotto_kasikoi_01, d_20_tyotto_kasikoi_02, d_20_tyotto_kasikoi_03, d_20_tyotto_kasikoi_04, d_20_tyotto_kasikoi_05, d_20_tyotto_kasikoi_06, d_20_tyotto_kasikoi_07, d_20_tyotto_kasikoi_08, d_20_tyotto_kasikoi_09, d_20_tyotto_kasikoi_10, d_20_tyotto_kasikoi_11, d_20_tyotto_kasikoi_12, d_20_tyotto_kasikoi_13, d_20_tyotto_kasikoi_14, d_20_tyotto_kasikoi_15, d_20_tyotto_kasikoi_16, d_20_tyotto_kasikoi_17, d_20_tyotto_kasikoi_18, d_20_tyotto_kasikoi_19, d_30_ookii_00, d_30_ookii_01, d_30_ookii_02, d_90_teuchi_00, d_90_teuchi_01, d_91_challenge_00, d_91_challenge_01, d_91_challenge_02, d_91_challenge_03, d_91_challenge_04, d_91_challenge_05 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
AC |
1 ms |
256 KB |
00_sample_01 |
AC |
1 ms |
256 KB |
01_minimal_00 |
AC |
1 ms |
256 KB |
01_minimal_01 |
AC |
1 ms |
256 KB |
01_minimal_02 |
AC |
1 ms |
256 KB |
01_minimal_03 |
AC |
1 ms |
256 KB |
10_detarame_00 |
AC |
1 ms |
256 KB |
10_detarame_01 |
AC |
1 ms |
256 KB |
10_detarame_02 |
AC |
1 ms |
256 KB |
10_detarame_03 |
AC |
1 ms |
256 KB |
10_detarame_04 |
AC |
1 ms |
256 KB |
10_detarame_05 |
AC |
1 ms |
256 KB |
10_detarame_06 |
AC |
1 ms |
256 KB |
10_detarame_07 |
AC |
1 ms |
256 KB |
10_detarame_08 |
AC |
1 ms |
256 KB |
10_detarame_09 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_00 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_01 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_02 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_03 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_04 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_05 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_06 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_07 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_08 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_09 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_10 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_11 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_12 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_13 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_14 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_15 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_16 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_17 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_18 |
AC |
1 ms |
256 KB |
20_tyotto_kasikoi_19 |
AC |
1 ms |
256 KB |
30_ookii_00 |
AC |
2 ms |
256 KB |
30_ookii_01 |
AC |
2 ms |
256 KB |
30_ookii_02 |
AC |
2 ms |
256 KB |
90_teuchi_00 |
AC |
1 ms |
256 KB |
90_teuchi_01 |
AC |
1 ms |
256 KB |
91_challenge_00 |
AC |
1 ms |
256 KB |
91_challenge_01 |
AC |
1 ms |
256 KB |
91_challenge_02 |
AC |
1 ms |
256 KB |
91_challenge_03 |
AC |
1 ms |
256 KB |
91_challenge_04 |
AC |
1 ms |
256 KB |
91_challenge_05 |
AC |
1 ms |
256 KB |
d_00_sample_00 |
AC |
1 ms |
256 KB |
d_00_sample_01 |
AC |
1 ms |
256 KB |
d_01_minimal_00 |
AC |
1 ms |
256 KB |
d_01_minimal_01 |
AC |
1 ms |
256 KB |
d_01_minimal_02 |
AC |
1 ms |
256 KB |
d_01_minimal_03 |
AC |
1 ms |
256 KB |
d_10_detarame_00 |
AC |
1 ms |
256 KB |
d_10_detarame_01 |
AC |
1 ms |
256 KB |
d_10_detarame_02 |
AC |
1 ms |
256 KB |
d_10_detarame_03 |
AC |
1 ms |
256 KB |
d_10_detarame_04 |
AC |
1 ms |
256 KB |
d_10_detarame_05 |
AC |
1 ms |
256 KB |
d_10_detarame_06 |
AC |
1 ms |
256 KB |
d_10_detarame_07 |
AC |
1 ms |
256 KB |
d_10_detarame_08 |
AC |
1 ms |
256 KB |
d_10_detarame_09 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_00 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_01 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_02 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_03 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_04 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_05 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_06 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_07 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_08 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_09 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_10 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_11 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_12 |
AC |
3 ms |
256 KB |
d_20_tyotto_kasikoi_13 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_14 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_15 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_16 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_17 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_18 |
AC |
1 ms |
256 KB |
d_20_tyotto_kasikoi_19 |
AC |
1 ms |
256 KB |
d_30_ookii_00 |
AC |
1 ms |
256 KB |
d_30_ookii_01 |
AC |
1 ms |
256 KB |
d_30_ookii_02 |
AC |
2 ms |
256 KB |
d_90_teuchi_00 |
AC |
1 ms |
256 KB |
d_90_teuchi_01 |
AC |
1 ms |
256 KB |
d_91_challenge_00 |
AC |
1 ms |
256 KB |
d_91_challenge_01 |
AC |
1 ms |
256 KB |
d_91_challenge_02 |
AC |
1 ms |
256 KB |
d_91_challenge_03 |
AC |
1 ms |
256 KB |
d_91_challenge_04 |
AC |
1 ms |
256 KB |
d_91_challenge_05 |
AC |
1 ms |
256 KB |