QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110360 | #5108. Prehistoric Programs | jyhptr | TL | 65ms | 4532kb | C++20 | 1.9kb | 2023-06-01 17:50:31 | 2023-06-01 17:50:33 |
Judging History
answer
// compile: make data
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#else
#define debug(x...) {};
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define double long double
#define int long long
#define MAXN 200010
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n; cin >> n;
struct node {
int minv, sum, id;
};
vector<node> pos, neg;
rep(i, 0, n) {
string s; cin >> s;
int minv = 0, sum = 0;
rep(j, 0, s.length()) {
if (s[j] == '(') sum++;
else sum--;
minv = min(minv, sum);
}
if (sum >= 0) pos.push_back({minv, sum, i+1});
else neg.push_back({minv, sum, i+1});
}
sort(pos.begin(), pos.end(), [](node a, node b) {
return a.minv > b.minv;
});
sort(neg.begin(), neg.end(), [](node a, node b) {
return a.minv < b.minv;
});
int sum = 0;
rep(i, 0, sz(pos)) {
if (sum + pos[i].minv < 0) {
print("impossible");
return 0;
}
sum += pos[i].sum;
}
rep(i, 0, sz(neg)) {
if (sum + neg[i].minv < 0) {
print("impossible");
return 0;
}
sum += neg[i].sum;
}
if (sum != 0) {
print("impossible");
return 0;
}
rep(i, 0, sz(pos)) cout << pos[i].id << endl;
rep(i, 0, sz(neg)) cout << neg[i].id << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 65ms
memory: 4532kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
31744 31767 31765 31764 31763 31759 31757 31755 31754 31753 31750 31747 31768 31743 31740 31738 31736 31734 31727 31726 31722 31721 31711 31710 31796 31818 31817 31815 31814 31812 31809 31806 31803 31801 31799 31798 31705 31795 31794 31793 31789 31787 31785 31784 31782 31777 31775 31634 31658 31656 ...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 6ms
memory: 3424kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
554 576 575 573 570 566 564 563 562 561 560 557 577 553 544 535 534 524 522 517 516 514 511 502 619 655 653 652 650 646 640 638 636 632 628 626 498 617 615 611 604 598 596 595 590 585 584 387 422 420 414 410 408 406 399 398 397 396 390 426 386 384 382 381 379 377 372 371 356 347 345 460 496 489 481 ...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 1ms
memory: 3380kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 2ms
memory: 3384kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 2ms
memory: 3400kb
input:
3 () ( )
output:
1 2 3
result:
ok good plan
Test #7:
score: 0
Accepted
time: 2ms
memory: 3408kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
5 ))( (() )( ( )
output:
2 4 3 1 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 2ms
memory: 3448kb
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: 0ms
memory: 3436kb
input:
500 ( ) ) ( )( ( ( ) ))( ( ( ( ( ) ) ( ( ) ( ( ) ( ()(() ( )()) ( ( ) ( )()(( ( ) ( ) ) ( ( ( ) ( ( ) ) )( ( ( ) ) ( ) ( ( ( ) ( ( ()))) ( ( ( ) ( ) ) ( ( ) ) ( ( ( ( ( () ( ( ( ( ( (( ) ( ( ) ( ( ( ) ()) ( ( ( ) ( ( ( ) ) ( ) ) ( ) ( ( ( ( ) ( ) ) ) ) ( ) )))()( ( ) ) ( ) )( ) ( ) ) )) ( ( ( ( ( ( ...
output:
334 290 296 297 304 308 309 311 315 318 320 321 325 327 329 330 288 338 339 340 343 344 345 348 349 350 351 353 356 357 360 362 262 232 234 239 1 241 242 243 247 248 249 251 253 254 256 258 366 264 265 268 269 271 274 275 277 282 283 284 285 286 287 467 434 435 436 437 438 439 440 442 443 445 449 45...
result:
ok good plan
Test #12:
score: 0
Accepted
time: 0ms
memory: 3472kb
input:
50 ) ) ((((()())())))(())(()) ()(((())) (((()))(() ()((( )) ) )()))(()(()())(((((() ( ) ) )(( )()(( ())())) (())))() ((( ))))(() ()(())(()))())() ) ) ( ( ( ( ((())()())())))(((()) ()( (()(())()((() ()(((()())))())()( ) )((() ( ) (( ) ()( ( ( ) )))((()) ) ()))()(((()(() (( ((()))(())(()())(()())())()...
output:
4 43 38 37 36 34 32 28 27 25 24 23 22 17 10 6 5 3 14 29 31 13 46 42 9 45 44 50 49 18 26 40 15 19 16 7 48 47 2 8 11 41 12 39 35 33 30 1 21 20
result:
ok good plan
Test #13:
score: 0
Accepted
time: 0ms
memory: 3392kb
input:
50 ) ( )()( ())( ()()(((((())( )(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...
output:
15 33 40 28 26 41 2 18 16 13 11 8 5 46 47 19 42 44 37 10 4 3 29 21 6 31 12 36 17 23 39 30 50 49 48 45 43 38 35 34 32 1 27 25 24 22 20 14 9 7
result:
ok good plan
Test #14:
score: 0
Accepted
time: 3ms
memory: 3420kb
input:
150 ))(()))(())(())))()))())()()()(())(((())))()))))() )))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...
output:
79 38 40 140 136 48 49 52 53 130 60 69 73 149 84 87 92 94 98 100 103 104 105 106 111 120 148 15 17 14 143 12 20 11 24 142 7 6 28 4 37 141 32 35 117 10 5 96 93 91 89 23 137 135 27 51 133 129 61 62 70 16 102 147 77 29 122 3 125 2 9 25 86 18 41 43 47 56 115 134 150 59 45 30 85 19 55 72 21 71 127 50 116...
result:
ok good plan
Test #15:
score: 0
Accepted
time: 3ms
memory: 3492kb
input:
150 )))( (() (())((())))(()))()(() ((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()()))))) ( ...
output:
98 51 52 56 58 61 64 2 70 86 87 89 94 66 100 104 118 121 127 128 129 141 142 148 149 150 37 26 32 19 36 15 14 10 42 49 46 4 5 44 8 50 16 18 117 113 112 107 145 102 23 29 55 84 80 75 74 53 136 63 39 76 114 82 34 90 88 85 144 21 13 140 41 7 62 45 122 40 81 96 111 79 97 12 125 116 123 22 108 20 139 115...
result:
ok good plan
Test #16:
score: 0
Accepted
time: 3ms
memory: 3460kb
input:
150 )()(( ) )))()))) )()())((()(()())((())()))(()))(())((((((((()()(())())(()(((()))())()((()((())())))))))()((()))))((()(((()(((((()))()))((()((()()))(())))))()))))()())()()())(())(())(()))())((((((()()()))()((((()))))))((())()))()(()((()(())(())(())()())(()) ()() ) (())()))(())(()((())()()())())((...
output:
106 60 65 67 68 74 75 81 84 89 92 93 97 98 99 5 108 110 111 115 117 118 122 123 129 130 131 136 140 149 48 36 30 27 45 50 52 55 8 58 127 11 57 124 19 24 9 26 1 31 100 42 63 56 70 46 88 119 146 128 14 15 120 82 114 35 91 101 37 107 133 43 32 90 78 12 44 61 112 7 64 109 125 72 134 85 71 77 95 20 116 1...
result:
ok good plan
Test #17:
score: 0
Accepted
time: 17ms
memory: 3500kb
input:
750 (()()((()((((())()((()))()()))()))(()()(()))(()(())()))(((((( ))))))) ) ((()()()(())((()(()())(())(((()((((()))(()(())((())(()())(())())))())))()(())()))((()(()((((()(()))(()())()((()()()))))(())())(())())())()((()( ) ) ( )()(((()(())))()))))(((((((()))()()()(()())))(()())(()(( ( ) )(())) ((())(...
output:
437 470 469 468 461 455 450 446 442 441 440 473 434 432 429 427 426 425 419 418 417 495 530 526 522 518 516 512 504 502 500 414 494 492 491 490 489 485 481 477 475 348 378 374 371 369 368 362 361 360 358 357 379 345 343 341 338 335 333 332 331 330 395 409 408 407 406 405 401 400 397 396 541 394 392 ...
result:
ok good plan
Test #18:
score: 0
Accepted
time: 3ms
memory: 3424kb
input:
100 ) ) ) ( ) ( ))))() ) ( ( ( ( ) ) ) ) ( ( ( ( ()) ( ) ) )(( ) ( ( ( ) ( ( ) ) ) ) ()(( ( ) ) ) )((( (((( ( ) ( ) (( ) ( ( ) ( ())(())) ) ) ( ) ( ( ( ( )))()() ) ( ( ( ( ) ( ) ) ) ( ) ) ) ) ( ) ( ( ) ( ) ( ( ( ) ) ( ) ) ( )(((( ) ) ()((()()(())))) ) (
output:
70 51 53 57 59 60 61 62 65 66 67 68 50 74 79 81 82 84 86 87 88 91 94 100 27 6 9 10 11 12 17 18 19 20 22 4 28 29 31 32 37 38 43 44 46 48 25 42 95 7 63 54 78 55 56 58 64 69 71 72 73 75 76 77 52 80 83 85 89 90 92 93 96 97 98 99 26 2 3 5 8 13 14 15 16 21 23 24 1 30 33 34 35 36 39 40 41 45 47 49
result:
ok good plan
Test #19:
score: 0
Accepted
time: 2ms
memory: 3388kb
input:
100 ) ()( ( ) ( ) ( ( ) ) )(() ) ))) ) ) ( ( ( ) ( ( ) ( ) ( ( ( ))( ( ( ))(( ( ) ( ))()) ) (() ) ) ( ) ( ( ) ) ( ) ( )) ( ( ) ) ( ) ) ) ) ( ()) ) ( ( ) ) ( ) ( )) ( ) ) ( ( ((( ( ( (() ) )()())(()((()((()) ( ) ) ( ( ) ) ( ) ( ) ( ))( ) ( ( ( ) ( (((())
output:
impossible
result:
ok impossible
Test #20:
score: 0
Accepted
time: 4ms
memory: 3376kb
input:
100 ) ) ()))(((( ))() ( ( ( ) ( ) ( ( ) () ( ( ) ) ( ) ( ( ) ) ) ( ) ) ( ( ) ) ( ) ) ) ) ( ( ) (( ( ( ) ) ( ( ) ( ) (()(( ) ( ) ) (()))()()())))()()(( ( ) ) ( ( ( ) ) ( ( ) ( ( ( ) ( ( ) )( ( ) ) ) ( (())())(() ) ) ( () (( ( ) ) ) ) ( ) ( ( ) ) ( ()) )(
output:
72 51 53 57 60 61 62 65 66 68 69 70 5 73 76 80 84 85 86 87 92 94 95 98 47 6 7 9 11 12 14 15 16 19 21 22 26 29 30 33 38 39 41 42 43 46 49 75 81 100 3 56 4 79 54 55 58 59 63 64 67 71 74 77 78 50 82 83 88 89 90 91 93 96 97 99 28 2 8 10 13 17 18 20 23 24 25 27 52 31 32 34 35 36 37 40 44 45 48 1
result:
ok good plan
Test #21:
score: 0
Accepted
time: 4ms
memory: 3404kb
input:
100 ( ( ) ( ) ( ( ( ( ) ) ) ) () )( ) ) ( ( ) ( ( ) ) ) ( ) ( ( )))) ( ) ( ) ( ( ( ()()( ) ()) ( ( ) ) ( ( ) ( ( ) ) ( ( ( ( ( ) ( ( ((( ) ) ) )))) ( ))( ) ) () ())() ) ) ( ))) ( )((()))( ( ((( (( ( ) ( ( ) ( ) ) () )() ) ) ()))()( )(())( ) ( ( ( ( )( )
output:
75 49 52 53 54 55 56 58 59 60 65 69 73 2 77 78 79 80 82 83 85 88 95 96 97 98 26 6 7 4 8 9 14 1 18 19 21 22 48 28 29 31 33 35 36 37 38 41 42 45 46 99 93 15 76 64 30 74 92 66 61 51 62 63 67 68 70 71 72 81 84 86 87 89 90 91 94 100 25 5 10 11 12 13 16 17 20 23 24 57 27 32 34 39 40 43 44 47 50 3
result:
ok good plan
Test #22:
score: 0
Accepted
time: 2ms
memory: 3428kb
input:
1000 (())())()(((())()())(((()(()))((()((((()())))())))))(()(()((())(((()))()(() ) ( ) () ) )((())))) ) ((((((()))()())))))((()( (( ()(()())))(() )() ( (( ( ) ) )(() )))( ) )) ( (())))) )(())(((())(((( ) ) ( ( ())))(()) ((( ( ((( ())()( ()()) ) ) ) ( ))))())( ) ))( ) ())(()(()))))()(()((())((((()())...
output:
impossible
result:
ok impossible
Test #23:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
1000 ))(())) ( )))( ) (( ()))()))))()()( ))))((((((((()()(())((()() ( ) )()(() ( ()))))() ( (()(()(((()())(((((((())()()())())(())()))))((()((())((((((()(()() )(()())((())) ((( ) ) ( )(( ( ( ) ( ) ()(())((( ( ) ( ( ) ()(()(()()(()()((()))())((()())))))((())(((()()(())(()()())(()()(((())()(()((((((((...
output:
impossible
result:
ok impossible
Test #24:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
4000 ( ) )) )()))))( ( ) ( ) ) ) )((()(( ( ) )()( ) ) ) ) ( ) ( ) ) ( ()))((()))))()((()( ( ))) ( ) ( ( ( ( ) )()(()()(()()))))()) ) ) )((( ) ) ) ) ( ( ) ))()()))((()) ( ( ) ( ))( ( ) ) ( ) ) ())( ) ( ( ( ) ())))(())((()(()()((()(( ( ) ) ( ) ) ) ) ) ) ) ) ( ) (()))))( ) ) ( ())))(((())()( ( ( ()( ( ...
output:
impossible
result:
ok impossible
Test #25:
score: -100
Time Limit Exceeded
input:
1000000 ) ( )()(((()))( ( ( ( ) ( ( ) ) (((())((()(()((()) ( ) )( ) ) ))))(()))()())(()((()))(()()()))()()()))))))))(())))((((()(()()))((((((()((((()()( ) (( ) ) ( ) ())()()(( ) )))(())((()))((()()))(()(())())))())))())))(()()( ( ()( ( ( ()() ) )) ) ( ( ( ) ) ) ( ) ( ) ) ) )(()))())) ( ) ))) ( ) ( (...
output:
641462 641493 641489 641488 641485 641484 641480 641479 641476 641474 641473 641471 641469 641465 641464 641494 641461 641460 641459 641456 641454 641453 641451 641448 641446 641445 641443 641441 641437 641436 641523 641555 641548 641547 641546 641545 641544 641542 641541 641536 641533 641532 641530...