QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#69637 | #5108. Prehistoric Programs | ricky0129 | TL | 96ms | 6612kb | C++14 | 2.0kb | 2022-12-29 03:38:32 | 2022-12-29 03:38:35 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define FOR(i,n) for(int i=0;i<n;i++)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second
const int MOD = (int)1e9+7;
struct obj{
string val;
int idx;
int sum, left,right;
obj(int sum=0,int left=0,int right=0) : sum(sum), left(left), right(right) {}
bool operator< (obj lhs) const {
if(sum<=0 == lhs.sum<=0){
if(sum<=0){
return tie(left,sum)<tie(lhs.left,lhs.sum);
}
else return tie(right,sum)<tie(lhs.right,lhs.sum);
}
return tie(sum)<tie(lhs.sum);
}
};
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin>>n;
vector<obj> A;
FOR(i,n){
string in;
cin>>in;
int curr = 0;
int mini = INT_MAX;
FOR(j,sz(in)){
if(in[j]=='(') curr++;
else curr--;
mini = min(mini,curr);
}
int sum = curr;
int maxi = INT_MAX;
curr = 0;
for(int j=sz(in)-1;j>=0;j--){
if(in[j]==')') curr++;
else curr--;
maxi = min(maxi,curr);
}
obj x(-sum,-mini,maxi);
x.idx = i+1;
x.val = in;
A.pb(x);
}
sort(A.begin(),A.end());
//for(auto x: A) cout<<x.val<<endl;
bool check = true;
int open = 0;
int close = 0;
for(auto x: A){
string in = x.val;
FOR(i,sz(in)){
if(in[i]==')') close++;
else open++;
if(close>open) check = false;
}
}
if(open!=close) check = false;
if(!check) cout<<"impossible\n";
else{
for(auto x: A){
cout<<x.idx<<endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 96ms
memory: 6612kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
4238 2458 48374 389 6754 18533 6986 32583 23456 169 5803 31692 34539 10427 26677 35132 30771 39743 41740 24373 46194 25061 45491 5699 34110 23312 31402 33777 41641 28794 23551 41639 6701 7365 6381 35743 22710 42121 40415 3880 34723 20865 11768 35499 40332 30949 34479 15279 31817 35256 27864 17649 25...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 28ms
memory: 3480kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
36 66 386 585 257 127 39 814 907 329 598 62 981 707 384 131 662 793 511 807 449 271 327 632 474 422 746 387 20 334 553 535 171 473 989 502 31 915 88 919 168 715 738 945 60 863 820 667 324 859 316 134 98 799 725 604 852 929 258 208 414 563 17 881 33 464 947 390 872 774 566 406 819 164 640 177 243 247...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 2ms
memory: 3452kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 2ms
memory: 3448kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 2ms
memory: 3460kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
3 () ( )
output:
2 1 3
result:
ok good plan
Test #7:
score: 0
Accepted
time: 2ms
memory: 3292kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 2ms
memory: 3308kb
input:
5 ))( (() )( ( )
output:
2 4 3 1 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 2ms
memory: 3456kb
input:
3 (( ))()) (
output:
1 3 2
result:
ok good plan
Test #10:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
6 ) () ()()() (( ) )
output:
impossible
result:
ok impossible
Test #11:
score: 0
Accepted
time: 11ms
memory: 3332kb
input:
500 ( ) ) ( )( ( ( ) ))( ( ( ( ( ) ) ( ( ) ( ( ) ( ()(() ( )()) ( ( ) ( )()(( ( ) ( ) ) ( ( ( ) ( ( ) ) )( ( ( ) ) ( ) ( ( ( ) ( ( ()))) ( ( ( ) ( ) ) ( ( ) ) ( ( ( ( ( () ( ( ( ( ( (( ) ( ( ) ( ( ( ) ()) ( ( ( ) ( ( ( ) ) ( ) ) ( ) ( ( ( ( ) ( ) ) ) ) ( ) )))()( ( ) ) ( ) )( ) ( ) ) )) ( ( ( ( ( ( ...
output:
479 329 311 232 483 199 297 414 211 357 80 265 177 253 271 159 158 157 156 153 442 431 160 440 439 269 437 436 166 435 434 268 264 172 262 429 284 456 124 288 287 286 128 129 130 131 132 133 285 452 136 152 283 139 282 141 449 143 378 277 275 274 445 149 381 406 207 208 209 210 413 214 412 411 410 4...
result:
ok good plan
Test #12:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
50 ) ) ((((()())())))(())(()) ()(((())) (((()))(() ()((( )) ) )()))(()(()())(((((() ( ) ) )(( )()(( ())())) (())))() ((( ))))(() ()(())(()))())() ) ) ( ( ( ( ((())()())())))(((()) ()( (()(())()((() ()(((()())))())()( ) )((() ( ) (( ) ()( ( ( ) )))((()) ) ()))()(((()(() (( ((()))(())(()())(()())())()...
output:
17 28 34 5 43 32 37 38 22 23 24 25 10 6 27 4 36 3 46 31 14 13 29 42 9 26 45 47 40 18 50 44 19 16 41 1 2 8 11 12 30 39 20 35 21 33 7 48 15 49
result:
ok good plan
Test #13:
score: 0
Accepted
time: 3ms
memory: 3464kb
input:
50 ) ( )()( ())( ()()(((((())( )(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...
output:
26 11 2 47 46 41 40 28 18 16 13 5 8 15 33 37 10 3 44 42 19 4 29 21 6 31 23 12 36 7 50 49 48 1 14 45 9 43 20 22 38 35 34 24 32 30 25 27 39 17
result:
ok good plan
Test #14:
score: 0
Accepted
time: 4ms
memory: 3576kb
input:
150 ))(()))(())(())))()))())()()()(())(((())))()))))() )))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...
output:
105 12 24 28 7 148 14 84 38 60 92 35 49 52 73 40 111 37 32 140 100 141 104 143 4 6 149 15 17 142 98 120 11 69 106 87 94 79 53 103 20 48 136 130 93 61 89 135 91 62 23 70 27 51 16 10 133 137 5 117 129 96 102 29 147 77 125 25 2 3 9 122 56 18 47 43 86 115 41 150 134 59 30 45 85 19 55 21 33 8 121 126 71 ...
result:
ok good plan
Test #15:
score: 0
Accepted
time: 5ms
memory: 3404kb
input:
150 )))( (() (())((())))(()))()(() ((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()()))))) ( ...
output:
129 149 150 121 70 148 104 19 51 26 2 36 37 44 46 56 58 61 87 89 94 127 128 141 8 14 10 5 49 142 100 32 98 86 64 118 52 66 15 4 42 23 29 16 112 75 145 55 102 84 107 117 113 80 50 18 39 74 63 34 82 53 114 136 76 88 90 85 144 21 140 13 41 7 62 45 40 111 97 96 79 139 116 81 20 78 108 130 137 125 73 133...
result:
ok good plan
Test #16:
score: 0
Accepted
time: 7ms
memory: 3432kb
input:
150 )()(( ) )))()))) )()())((()(()())((())()))(()))(())((((((((()()(())())(()(((()))())()((()((())())))))))()((()))))((()(((()(((((()))()))((()((()()))(())))))()))))()())()()())(())(())(()))())((((((()()()))()((((()))))))((())()))()(()((()(())(())(())()())(()) ()() ) (())()))(())(()((())()()())())((...
output:
129 131 84 115 117 45 52 92 75 140 136 36 67 74 60 30 55 81 48 123 118 97 149 99 8 106 111 108 50 27 122 130 110 58 65 93 89 68 98 5 63 127 100 42 46 88 70 24 56 1 31 11 124 19 26 57 9 114 15 101 35 120 146 82 119 128 14 91 133 107 37 32 43 12 90 78 44 112 61 7 64 109 125 85 72 144 41 22 20 28 95 16...
result:
ok good plan
Test #17:
score: 0
Accepted
time: 11ms
memory: 3544kb
input:
750 (()()((()((((())()((()))()()))()))(()()(()))(()(())()))(((((( ))))))) ) ((()()()(())((()(()())(())(((()((((()))(()(())((())(()())(())())))())))()(())()))((()(()((((()(()))(()())()((()()()))))(())())(())())())()((()( ) ) ( )()(((()(())))()))))(((((((()))()()()(()())))(()())(()(( ( ) )(())) ((())(...
output:
468 390 396 4 122 1 601 657 274 79 180 158 526 485 730 547 25 571 131 530 41 166 43 103 246 164 55 56 230 341 494 418 395 481 408 606 406 243 622 605 495 250 624 469 281 625 238 587 618 160 609 255 612 258 225 259 265 162 263 264 650 176 492 181 182 184 185 186 172 654 191 169 653 661 651 195 470 64...
result:
ok good plan
Test #18:
score: 0
Accepted
time: 4ms
memory: 3300kb
input:
100 ) ) ) ( ) ( ))))() ) ( ( ( ( ) ) ) ) ( ( ( ( ()) ( ) ) )(( ) ( ( ( ) ( ( ) ) ) ) ()(( ( ) ) ) )((( (((( ( ) ( ) (( ) ( ( ) ( ())(())) ) ) ( ) ( ( ( ( )))()() ) ( ( ( ( ) ( ) ) ) ( ) ) ) ) ( ) ( ( ) ( ) ( ( ( ) ) ( ) ) ( )(((( ) ) ()((()()(())))) ) (
output:
43 48 66 32 38 44 46 50 53 57 59 60 61 62 65 51 67 68 70 74 79 81 82 84 86 87 88 91 94 100 17 10 22 9 20 19 6 18 11 4 27 28 31 29 12 37 95 42 25 63 7 73 78 77 76 80 75 16 83 8 85 5 89 90 92 93 3 96 97 98 99 2 1 30 33 34 35 36 39 40 41 45 26 47 49 24 72 52 23 55 56 58 21 64 15 14 69 13 71 54
result:
ok good plan
Test #19:
score: 0
Accepted
time: 2ms
memory: 3328kb
input:
100 ) ()( ( ) ( ) ( ( ) ) )(() ) ))) ) ) ( ( ( ) ( ( ) ( ) ( ( ( ))( ( ( ))(( ( ) ( ))()) ) (() ) ) ( ) ( ( ) ) ( ) ( )) ( ( ) ) ( ) ) ) ) ( ()) ) ( ( ) ) ( ) ( )) ( ) ) ( ( ((( ( ( (() ) )()())(()((()((()) ( ) ) ( ( ) ) ( ) ( ) ( ))( ) ( ( ( ) ( (((())
output:
impossible
result:
ok impossible
Test #20:
score: 0
Accepted
time: 4ms
memory: 3364kb
input:
100 ) ) ()))(((( ))() ( ( ( ) ( ) ( ( ) () ( ( ) ) ( ) ( ( ) ) ) ( ) ) ( ( ) ) ( ) ) ) ) ( ( ) (( ( ( ) ) ( ( ) ( ) (()(( ) ( ) ) (()))()()())))()()(( ( ) ) ( ( ( ) ) ( ( ) ( ( ( ) ( ( ) )( ( ) ) ) ( (())())(() ) ) ( () (( ( ) ) ) ) ( ) ( ( ) ) ( ()) )(
output:
51 41 86 73 26 72 29 30 70 69 33 68 66 65 62 38 39 61 42 43 60 57 46 47 53 49 16 6 7 92 9 87 11 12 5 15 94 84 19 95 21 22 80 76 98 14 85 100 81 75 3 56 4 89 77 78 79 23 20 82 83 18 17 13 10 88 24 90 91 8 93 96 97 2 99 1 64 52 48 54 55 45 58 59 44 40 37 63 50 36 35 67 34 32 31 71 28 27 74 25
result:
ok good plan
Test #21:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
100 ( ( ) ( ) ( ( ( ( ) ) ) ) () )( ) ) ( ( ) ( ( ) ) ) ( ) ( ( )))) ( ) ( ) ( ( ( ()()( ) ()) ( ( ) ) ( ( ) ( ( ) ) ( ( ( ( ( ) ( ( ((( ) ) ) )))) ( ))( ) ) () ())() ) ) ( ))) ( )((()))( ( ((( (( ( ) ( ( ) ( ) ) () )() ) ) ()))()( )(())( ) ( ( ( ( )( )
output:
60 78 79 83 80 46 45 82 42 41 49 37 36 35 85 33 31 48 2 52 53 54 55 56 77 58 59 75 73 65 21 97 96 95 98 9 8 18 19 7 6 22 4 1 26 28 29 38 88 14 69 15 99 76 93 92 66 89 70 87 94 81 91 90 84 72 100 71 86 34 3 5 10 11 12 13 16 17 20 23 24 25 27 32 68 39 40 43 44 47 50 51 57 61 62 63 67 74 30 64
result:
ok good plan
Test #22:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
1000 (())())()(((())()())(((()(()))((()((((()())))())))))(()(()((())(((()))()(() ) ( ) () ) )((())))) ) ((((((()))()())))))((()( (( ()(()())))(() )() ( (( ( ) ) )(() )))( ) )) ( (())))) )(())(((())(((( ) ) ( ( ())))(()) ((( ( ((( ())()( ()()) ) ) ) ( ))))())( ) ))( ) ())(()(()))))()(()((())((((()())...
output:
impossible
result:
ok impossible
Test #23:
score: 0
Accepted
time: 1ms
memory: 3388kb
input:
1000 ))(())) ( )))( ) (( ()))()))))()()( ))))((((((((()()(())((()() ( ) )()(() ( ()))))() ( (()(()(((()())(((((((())()()())())(())()))))((()((())((((((()(()() )(()())((())) ((( ) ) ( )(( ( ( ) ( ) ()(())((( ( ) ( ( ) ()(()(()()(()()((()))())((()())))))((())(((()()(())(()()())(()()(((())()(()((((((((...
output:
impossible
result:
ok impossible
Test #24:
score: 0
Accepted
time: 4ms
memory: 3544kb
input:
4000 ( ) )) )()))))( ( ) ( ) ) ) )((()(( ( ) )()( ) ) ) ) ( ) ( ) ) ( ()))((()))))()((()( ( ))) ( ) ( ( ( ( ) )()(()()(()()))))()) ) ) )((( ) ) ) ) ( ( ) ))()()))((()) ( ( ) ( ))( ( ) ) ( ) ) ())( ) ( ( ( ) ())))(())((()(()()((()(( ( ) ) ( ) ) ) ) ) ) ) ) ( ) (()))))( ) ) ( ())))(((())()( ( ( ()( ( ...
output:
impossible
result:
ok impossible
Test #25:
score: -100
Time Limit Exceeded
input:
1000000 ) ( )()(((()))( ( ( ( ) ( ( ) ) (((())((()(()((()) ( ) )( ) ) ))))(()))()())(()((()))(()()()))()()()))))))))(())))((((()(()()))((((((()((((()()( ) (( ) ) ( ) ())()()(( ) )))(())((()))((()()))(()(())())))())))())))(()()( ( ()( ( ( ()() ) )) ) ( ( ( ) ) ) ( ) ( ) ) ) )(()))())) ( ) ))) ( ) ( (...
output:
264227 770337 898404 83071 269214 857929 897909 731069 196234 352796 904916 134097 308325 501576 309146 592970 992894 748267 675083 900795 267140 619800 507757 610823 714320 902203 833824 769249 932913 799635 470977 175996 703503 799479 25080 164427 705720 356849 385146 999836 920721 466467 637563 6...