Submission #3466447
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 a[160][160]={0}; int ans; int ddx[6]={1,0,-1,-1,0,1}; int ddy[6]={1,1,0,-1,-1,0}; queue<ppap> qu; void dfs(int x,int y,int zan){ qu.push(mp(0,mp(x,y))); while(qu.size()){ ppap r=qu.front(); qu.pop(); pa z=r.second; if(a[z.first][z.second]>0) continue; a[z.first][z.second]=1; ans++; if(r.first<zan)for(int i=0;i<6;i++)qu.push(mp(r.first+1,mp(z.first+ddx[i],z.second+ddy[i]))); } } string dp[60][60]; int oknum[60][60]={0}; int ok2[60][60]={0}; string hi(string s,string t){ if(s.length()>t.length())return s; if(s.length()<t.length())return t; if(s>t) return s; return t; } signed main(){ string s; cin>>s; int l=s.length(); for(int i=0;i<60;i++)for(int j=0;j<60;j++)dp[i][j]=""; for(int i=0;i<l;i++)for(int j=i+1;j<=l;j++){ bool bo=1; for(int k=i;k<j;k++)if(s[k]==',' ||s[k]=='L' ||s[k]=='R' ||s[k]=='(' ||s[k]==')' )bo=0; if(i+1<j && s[i]=='0') bo=false; if(bo){ oknum[i][j]=1; string s1=s.substr(i,j-i); for(int k=0;k<s1.length();k++)if(s1[k]=='?')s1[k]='9'; dp[i][j]=s1; } } for(int d=1;d<=l;d++)for(int i=0;i<=l-d;i++){ int j=i+d; if(oknum[i][j]) continue; if(d>=6 && (s[i]=='R'|| s[i]=='?') &&(s[i+1]=='('|| s[i+1]=='?') &&(s[j-1]==')'|| s[j-1]=='?') ){ for(int k=i+3;k<=j-3;k++)if(s[k]==',' || s[k]=='?')if(dp[i+2][k]!="" &&dp[k+1][j-1]!=""){ dp[i][j]=hi(dp[i][j],dp[k+1][j-1]); } } if(d>=6 && (s[i]=='L'|| s[i]=='?') &&(s[i+1]=='('|| s[i+1]=='?') &&(s[j-1]==')'|| s[j-1]=='?') ){ for(int k=i+3;k<=j-3;k++)if(s[k]==',' || s[k]=='?')if(dp[i+2][k]!="" &&dp[k+1][j-1]!=""){ dp[i][j]=hi(dp[i][j],dp[i+2][k]); } } } if(dp[0][l]=="") cout<<"invalid"<<endl; else cout<<dp[0][l]<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - LR |
User | smiken |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 10649 Byte |
Status | AC |
Exec Time | 4 ms |
Memory | 384 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 100 / 100 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 00_sample_04, 00_sample_05, 00_sample_06, 01_zero_00, 01_zero_01, 01_zero_02, 01_zero_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_neniri_00, 20_neniri_01, 20_neniri_02, 20_neniri_03, 20_neniri_04, 20_neniri_05, 20_neniri_06, 20_neniri_07, 20_neniri_08, 20_neniri_09, 20_neniri_10, 20_neniri_11, 20_neniri_12, 20_neniri_13, 20_neniri_14, 20_neniri_15, 20_neniri_16, 20_neniri_17, 20_neniri_18, 20_neniri_19, 20_neniri_20, 20_neniri_21, 20_neniri_22, 20_neniri_23, 20_neniri_24, 20_neniri_25, 20_neniri_26, 20_neniri_27, 20_neniri_28, 20_neniri_29, 20_neniri_30, 20_neniri_31, 20_neniri_32, 20_neniri_33, 20_neniri_34, 20_neniri_35, 20_neniri_36, 20_neniri_37, 20_neniri_38, 20_neniri_39, 20_neniri_40, 20_neniri_41, 20_neniri_42, 20_neniri_43, 20_neniri_44, 20_neniri_45, 20_neniri_46, 20_neniri_47, 20_neniri_48, 20_neniri_49, 20_neniri_50, 20_neniri_51, 20_neniri_52, 20_neniri_53, 20_neniri_54, 20_neniri_55, 20_neniri_56, 20_neniri_57, 20_neniri_58, 20_neniri_59, 20_neniri_60, 20_neniri_61, 20_neniri_62, 20_neniri_63, 20_neniri_64, 20_neniri_65, 20_neniri_66, 20_neniri_67, 20_neniri_68, 20_neniri_69, 20_neniri_70, 20_neniri_71, 20_neniri_72, 20_neniri_73, 20_neniri_74, 20_neniri_75, 20_neniri_76, 20_neniri_77, 20_neniri_78, 20_neniri_79, 30_hikaku_00, 30_hikaku_01, 30_hikaku_02, 30_hikaku_03, 30_hikaku_04, 30_hikaku_05, 30_hikaku_06, 30_hikaku_07, 30_hikaku_08, 30_hikaku_09, 31_hikaku_hatena_00, 31_hikaku_hatena_01, 31_hikaku_hatena_02, 31_hikaku_hatena_03, 31_hikaku_hatena_04, 31_hikaku_hatena_05, 31_hikaku_hatena_06, 31_hikaku_hatena_07, 31_hikaku_hatena_08, 31_hikaku_hatena_09, 40_ookii_00, 40_ookii_01, 40_ookii_02, 40_ookii_03, 40_ookii_04, 40_ookii_05, 40_ookii_06, 50_osii_00, 50_osii_01, 50_osii_02, 50_osii_03, 50_osii_04, 50_osii_05, 50_osii_06, 50_osii_07, 50_osii_08, 50_osii_09, 50_osii_10, 50_osii_11, 50_osii_12, 50_osii_13, 50_osii_14, 50_osii_15, 50_osii_16, 50_osii_17, 50_osii_18, 50_osii_19, 90_challenge_00, 90_challenge_01, 90_challenge_02, 90_challenge_03, 90_challenge_04, 90_challenge_05, 90_challenge_06, 90_challenge_07, 90_challenge_08, 90_challenge_09 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_sample_00 | AC | 1 ms | 256 KB |
00_sample_01 | AC | 1 ms | 256 KB |
00_sample_02 | AC | 1 ms | 256 KB |
00_sample_03 | AC | 1 ms | 256 KB |
00_sample_04 | AC | 1 ms | 384 KB |
00_sample_05 | AC | 2 ms | 384 KB |
00_sample_06 | AC | 2 ms | 384 KB |
01_zero_00 | AC | 1 ms | 256 KB |
01_zero_01 | AC | 1 ms | 256 KB |
01_zero_02 | AC | 1 ms | 256 KB |
01_zero_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_neniri_00 | AC | 1 ms | 256 KB |
20_neniri_01 | AC | 1 ms | 256 KB |
20_neniri_02 | AC | 1 ms | 256 KB |
20_neniri_03 | AC | 1 ms | 256 KB |
20_neniri_04 | AC | 1 ms | 256 KB |
20_neniri_05 | AC | 1 ms | 256 KB |
20_neniri_06 | AC | 1 ms | 256 KB |
20_neniri_07 | AC | 1 ms | 256 KB |
20_neniri_08 | AC | 1 ms | 256 KB |
20_neniri_09 | AC | 1 ms | 256 KB |
20_neniri_10 | AC | 1 ms | 256 KB |
20_neniri_11 | AC | 1 ms | 256 KB |
20_neniri_12 | AC | 1 ms | 256 KB |
20_neniri_13 | AC | 1 ms | 256 KB |
20_neniri_14 | AC | 1 ms | 256 KB |
20_neniri_15 | AC | 1 ms | 256 KB |
20_neniri_16 | AC | 1 ms | 256 KB |
20_neniri_17 | AC | 1 ms | 256 KB |
20_neniri_18 | AC | 1 ms | 256 KB |
20_neniri_19 | AC | 1 ms | 256 KB |
20_neniri_20 | AC | 1 ms | 256 KB |
20_neniri_21 | AC | 1 ms | 256 KB |
20_neniri_22 | AC | 1 ms | 256 KB |
20_neniri_23 | AC | 1 ms | 256 KB |
20_neniri_24 | AC | 1 ms | 256 KB |
20_neniri_25 | AC | 1 ms | 256 KB |
20_neniri_26 | AC | 1 ms | 256 KB |
20_neniri_27 | AC | 1 ms | 256 KB |
20_neniri_28 | AC | 1 ms | 256 KB |
20_neniri_29 | AC | 4 ms | 256 KB |
20_neniri_30 | AC | 1 ms | 256 KB |
20_neniri_31 | AC | 1 ms | 256 KB |
20_neniri_32 | AC | 1 ms | 256 KB |
20_neniri_33 | AC | 1 ms | 256 KB |
20_neniri_34 | AC | 1 ms | 256 KB |
20_neniri_35 | AC | 1 ms | 256 KB |
20_neniri_36 | AC | 1 ms | 256 KB |
20_neniri_37 | AC | 1 ms | 256 KB |
20_neniri_38 | AC | 1 ms | 256 KB |
20_neniri_39 | AC | 1 ms | 256 KB |
20_neniri_40 | AC | 1 ms | 256 KB |
20_neniri_41 | AC | 1 ms | 256 KB |
20_neniri_42 | AC | 1 ms | 256 KB |
20_neniri_43 | AC | 1 ms | 256 KB |
20_neniri_44 | AC | 1 ms | 256 KB |
20_neniri_45 | AC | 1 ms | 256 KB |
20_neniri_46 | AC | 1 ms | 256 KB |
20_neniri_47 | AC | 1 ms | 256 KB |
20_neniri_48 | AC | 1 ms | 256 KB |
20_neniri_49 | AC | 1 ms | 256 KB |
20_neniri_50 | AC | 1 ms | 256 KB |
20_neniri_51 | AC | 1 ms | 256 KB |
20_neniri_52 | AC | 1 ms | 256 KB |
20_neniri_53 | AC | 1 ms | 256 KB |
20_neniri_54 | AC | 1 ms | 256 KB |
20_neniri_55 | AC | 1 ms | 256 KB |
20_neniri_56 | AC | 1 ms | 256 KB |
20_neniri_57 | AC | 1 ms | 256 KB |
20_neniri_58 | AC | 1 ms | 256 KB |
20_neniri_59 | AC | 1 ms | 256 KB |
20_neniri_60 | AC | 1 ms | 256 KB |
20_neniri_61 | AC | 1 ms | 256 KB |
20_neniri_62 | AC | 1 ms | 256 KB |
20_neniri_63 | AC | 1 ms | 256 KB |
20_neniri_64 | AC | 1 ms | 256 KB |
20_neniri_65 | AC | 1 ms | 256 KB |
20_neniri_66 | AC | 1 ms | 256 KB |
20_neniri_67 | AC | 1 ms | 256 KB |
20_neniri_68 | AC | 1 ms | 256 KB |
20_neniri_69 | AC | 1 ms | 256 KB |
20_neniri_70 | AC | 1 ms | 256 KB |
20_neniri_71 | AC | 1 ms | 256 KB |
20_neniri_72 | AC | 1 ms | 256 KB |
20_neniri_73 | AC | 1 ms | 256 KB |
20_neniri_74 | AC | 1 ms | 256 KB |
20_neniri_75 | AC | 1 ms | 256 KB |
20_neniri_76 | AC | 1 ms | 256 KB |
20_neniri_77 | AC | 1 ms | 256 KB |
20_neniri_78 | AC | 1 ms | 256 KB |
20_neniri_79 | AC | 1 ms | 256 KB |
30_hikaku_00 | AC | 1 ms | 256 KB |
30_hikaku_01 | AC | 1 ms | 256 KB |
30_hikaku_02 | AC | 1 ms | 256 KB |
30_hikaku_03 | AC | 1 ms | 256 KB |
30_hikaku_04 | AC | 1 ms | 256 KB |
30_hikaku_05 | AC | 1 ms | 256 KB |
30_hikaku_06 | AC | 1 ms | 256 KB |
30_hikaku_07 | AC | 1 ms | 256 KB |
30_hikaku_08 | AC | 1 ms | 256 KB |
30_hikaku_09 | AC | 1 ms | 256 KB |
31_hikaku_hatena_00 | AC | 2 ms | 384 KB |
31_hikaku_hatena_01 | AC | 2 ms | 384 KB |
31_hikaku_hatena_02 | AC | 2 ms | 384 KB |
31_hikaku_hatena_03 | AC | 2 ms | 384 KB |
31_hikaku_hatena_04 | AC | 2 ms | 384 KB |
31_hikaku_hatena_05 | AC | 2 ms | 384 KB |
31_hikaku_hatena_06 | AC | 2 ms | 384 KB |
31_hikaku_hatena_07 | AC | 2 ms | 384 KB |
31_hikaku_hatena_08 | AC | 2 ms | 384 KB |
31_hikaku_hatena_09 | AC | 2 ms | 384 KB |
40_ookii_00 | AC | 2 ms | 384 KB |
40_ookii_01 | AC | 1 ms | 384 KB |
40_ookii_02 | AC | 1 ms | 384 KB |
40_ookii_03 | AC | 2 ms | 384 KB |
40_ookii_04 | AC | 2 ms | 384 KB |
40_ookii_05 | AC | 1 ms | 384 KB |
40_ookii_06 | AC | 1 ms | 384 KB |
50_osii_00 | AC | 1 ms | 256 KB |
50_osii_01 | AC | 1 ms | 256 KB |
50_osii_02 | AC | 1 ms | 256 KB |
50_osii_03 | AC | 1 ms | 256 KB |
50_osii_04 | AC | 1 ms | 256 KB |
50_osii_05 | AC | 1 ms | 256 KB |
50_osii_06 | AC | 1 ms | 256 KB |
50_osii_07 | AC | 1 ms | 256 KB |
50_osii_08 | AC | 1 ms | 256 KB |
50_osii_09 | AC | 1 ms | 256 KB |
50_osii_10 | AC | 1 ms | 256 KB |
50_osii_11 | AC | 1 ms | 256 KB |
50_osii_12 | AC | 1 ms | 256 KB |
50_osii_13 | AC | 1 ms | 256 KB |
50_osii_14 | AC | 1 ms | 256 KB |
50_osii_15 | AC | 1 ms | 256 KB |
50_osii_16 | AC | 2 ms | 256 KB |
50_osii_17 | AC | 1 ms | 256 KB |
50_osii_18 | AC | 1 ms | 256 KB |
50_osii_19 | AC | 1 ms | 256 KB |
90_challenge_00 | AC | 1 ms | 256 KB |
90_challenge_01 | AC | 1 ms | 256 KB |
90_challenge_02 | AC | 1 ms | 256 KB |
90_challenge_03 | AC | 1 ms | 256 KB |
90_challenge_04 | AC | 1 ms | 256 KB |
90_challenge_05 | AC | 1 ms | 256 KB |
90_challenge_06 | AC | 1 ms | 256 KB |
90_challenge_07 | AC | 1 ms | 256 KB |
90_challenge_08 | AC | 1 ms | 256 KB |
90_challenge_09 | AC | 1 ms | 384 KB |