QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#116431 | #5108. Prehistoric Programs | duongnc000 | WA | 27ms | 5580kb | C++20 | 2.4kb | 2023-06-28 22:51:46 | 2023-06-28 22:51:47 |
Judging History
answer
/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;
const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n;
pii p[mxN];
vi pos, neg;
bool cmp(int x, int y) {
pii a = p[x], b = p[y];
if(a.ff != b.ff) return (a.ff < b.ff);
else return (a.ss > b.ss);
}
void kill() {
cout << "impossible" << endl;
exit(0);
}
void solve() {
cin >> n;
for(int i = 1; i <= n; ++i) {
string s; cin >> s;
int sum = 0;
for(char c : s)
sum += (c == '(' ? 1 : -1);
if(sum >= 0) {
int cur_sum = 0, cur_min = 0;
for(char c : s) {
cur_sum += (c == '(' ? 1 : -1);
cur_min = min(cur_min, cur_sum);
}
pos.emplace_back(i);
p[i] = {-cur_min, cur_sum};
}
else {
reverse(all(s));
int cur_sum = 0, cur_min = 0;
for(char c : s) {
cur_sum += (c == ')' ? 1 : -1);
cur_min = min(cur_min, cur_sum);
}
neg.emplace_back(i);
p[i] = {-cur_min, cur_sum};
}
}
sort(all(pos), cmp);
sort(all(neg), cmp);
int cur_sum_pos = 0;
for(int &val : pos) {
if(p[val].ff > cur_sum_pos)
kill();
cur_sum_pos += p[val].ss;
}
int cur_sum_neg = 0;
for(int &val : neg) {
if(p[val].ff > cur_sum_neg)
kill();
cur_sum_neg += p[val].ss;
}
if(cur_sum_pos != cur_sum_neg)
kill();
reverse(all(neg));
pos.insert(pos.end(), all(neg));
for(int &val : pos)
cout << val << "\n";
}
signed main() {
#ifndef CDuongg
if(fopen(taskname".inp", "r"))
assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
freopen("bai3.inp", "r", stdin);
freopen("bai3.out", "w", stdout);
auto start = chrono::high_resolution_clock::now();
#endif
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; //cin >> t;
while(t--) solve();
#ifdef CDuongg
auto end = chrono::high_resolution_clock::now();
cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 11ms
memory: 4016kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
41248 4238 13809 5338 27609 2458 389 48374 48749 6754 18533 42979 14096 6986 5803 32583 23456 31692 3405 169 26677 9225 26695 10427 38930 43508 34539 35132 30771 21764 25061 2253 24373 39743 46194 11398 46429 41740 31402 34110 35039 33777 45491 5699 23312 28794 41641 41639 6381 463 9790 35743 6701 3...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 2ms
memory: 3472kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
36 13 66 386 966 585 286 257 127 83 39 476 595 329 598 214 814 907 427 62 981 707 384 662 131 807 793 511 80 271 869 449 767 638 379 746 474 239 327 422 632 20 387 715 535 31 975 88 989 473 296 168 171 334 553 345 502 919 915 464 164 563 134 738 566 731 725 575 481 604 686 208 258 177 667 640 827 60...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 1ms
memory: 3408kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 1ms
memory: 3416kb
input:
3 () ( )
output:
2 1 3
result:
ok good plan
Test #7:
score: 0
Accepted
time: 0ms
memory: 3476kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
5 ))( (() )( ( )
output:
2 4 3 1 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
3 (( ))()) (
output:
1 3 2
result:
ok good plan
Test #10:
score: 0
Accepted
time: 0ms
memory: 3416kb
input:
6 ) () ()()() (( ) )
output:
impossible
result:
ok impossible
Test #11:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
500 ( ) ) ( )( ( ( ) ))( ( ( ( ( ) ) ( ( ) ( ( ) ( ()(() ( )()) ( ( ) ( )()(( ( ) ( ) ) ( ( ( ) ( ( ) ) )( ( ( ) ) ( ) ( ( ( ) ( ( ()))) ( ( ( ) ( ) ) ( ( ) ) ( ( ( ( ( () ( ( ( ( ( (( ) ( ( ) ( ( ( ) ()) ( ( ( ) ( ( ( ) ) ( ) ) ( ) ( ( ( ( ) ( ) ) ) ) ( ) )))()( ( ) ) ( ) )( ) ( ) ) )) ( ( ( ( ( ( ...
output:
311 329 479 232 443 483 199 80 414 297 177 265 253 357 350 211 325 290 362 296 308 309 351 315 318 320 321 340 327 349 345 330 353 334 338 344 343 339 262 234 239 1 241 242 243 247 248 249 251 254 256 258 288 264 268 269 271 274 275 277 282 283 284 285 286 287 459 428 429 431 434 435 436 437 439 440...
result:
ok good plan
Test #12:
score: 0
Accepted
time: 1ms
memory: 3500kb
input:
50 ) ) ((((()())())))(())(()) ()(((())) (((()))(() ()((( )) ) )()))(()(()())(((((() ( ) ) )(( )()(( ())())) (())))() ((( ))))(() ()(())(()))())() ) ) ( ( ( ( ((())()())())))(((()) ()( (()(())()((() ()(((()())))())()( ) )((() ( ) (( ) ()( ( ( ) )))((()) ) ()))()(((()(() (( ((()))(())(()())(()())())()...
output:
6 17 28 43 5 34 4 38 37 36 32 27 25 24 23 22 10 3 46 31 14 13 29 42 9 26 45 47 40 18 50 44 8 11 12 1 20 21 30 33 35 39 41 2 19 16 48 7 15 49
result:
ok good plan
Test #13:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
50 ) ( )()( ())( ()()(((((())( )(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...
output:
26 5 11 47 46 8 40 13 28 16 18 2 41 15 33 37 19 42 44 10 4 3 29 21 6 31 23 12 7 9 14 20 22 24 25 27 1 32 34 35 38 43 45 48 49 50 30 39 17 36
result:
ok good plan
Test #14:
score: 0
Accepted
time: 1ms
memory: 3428kb
input:
150 ))(()))(())(())))()))())()()()(())(((())))()))))() )))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...
output:
17 105 142 98 12 24 120 7 28 148 87 84 69 60 38 14 11 106 92 6 111 52 73 49 79 94 140 141 149 40 37 35 32 143 100 4 15 104 130 20 136 53 48 103 93 61 89 135 91 62 23 51 70 27 133 10 16 129 117 137 96 5 102 29 77 147 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: 1ms
memory: 3488kb
input:
150 )))( (() (())((())))(()))()(() ((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()()))))) ( ...
output:
49 129 149 142 100 150 70 121 32 64 86 51 98 104 19 148 127 2 5 61 58 56 8 87 52 10 89 46 94 44 14 141 37 36 118 128 26 66 4 15 42 23 29 16 112 145 75 55 107 117 102 84 113 80 50 18 39 74 63 34 82 53 76 114 136 88 90 85 144 21 140 13 41 7 62 45 40 111 97 96 79 139 116 81 20 78 108 137 130 125 133 73...
result:
ok good plan
Test #16:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
150 )()(( ) )))()))) )()())((()(()())((())()))(()))(())((((((((()()(())())(()(((()))())()((()((())())))))))()((()))))((()(((()(((((()))()))((()((()()))(())))))()))))()())()()())(())(())(()))())((((((()()()))()((((()))))))((())()))()(()((()(())(())(())()())(()) ()() ) (())()))(())(()((())()()())())((...
output:
129 50 131 84 115 27 117 45 122 92 52 130 75 140 48 55 93 106 58 60 81 65 67 74 97 99 108 36 110 111 30 118 123 136 8 149 98 5 89 68 63 127 100 88 42 46 70 24 1 11 31 56 124 57 19 26 9 114 15 101 35 120 146 82 119 91 128 14 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: 2ms
memory: 3452kb
input:
750 (()()((()((((())()((()))()()))()))(()()(()))(()(())()))(((((( ))))))) ) ((()()()(())((()(()())(())(((()((((()))(()(())((())(()())(())())))())))()(())()))((()(()((((()(()))(()())()((()()()))))(())())(())())())()((()( ) ) ( )()(((()(())))()))))(((((((()))()()()(()())))(()())(()(( ( ) )(())) ((())(...
output:
468 163 390 379 204 396 707 590 585 4 122 1 405 657 658 601 79 180 34 274 104 473 158 149 681 571 547 504 526 730 269 705 485 108 25 230 341 103 426 395 156 406 218 246 382 494 41 43 481 408 418 131 55 56 606 166 164 530 357 378 358 581 361 362 578 574 368 369 371 374 624 326 636 622 287 618 294 612...
result:
ok good plan
Test #18:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
100 ) ) ) ( ) ( ))))() ) ( ( ( ( ) ) ) ) ( ( ( ( ()) ( ) ) )(( ) ( ( ( ) ( ( ) ) ) ) ()(( ( ) ) ) )((( (((( ( ) ( ) (( ) ( ( ) ( ())(())) ) ) ( ) ( ( ( ( )))()() ) ( ( ( ( ) ( ) ) ) ( ) ) ) ) ( ) ( ( ) ( ) ( ( ( ) ) ( ) ) ( )(((( ) ) ()((()()(())))) ) (
output:
43 48 37 68 53 57 59 60 61 62 65 66 67 50 70 74 79 81 82 84 86 87 88 91 94 100 4 6 9 10 11 12 17 18 19 20 22 27 28 29 31 32 38 44 46 51 95 42 25 49 47 45 41 40 39 36 35 34 33 30 1 24 23 21 16 15 14 13 8 5 3 2 26 99 98 97 96 93 92 90 89 85 83 80 52 77 76 75 73 72 71 69 64 58 56 55 78 54 63 7
result:
ok good plan
Test #19:
score: 0
Accepted
time: 1ms
memory: 3412kb
input:
100 ) ()( ( ) ( ) ( ( ) ) )(() ) ))) ) ) ( ( ( ) ( ( ) ( ) ( ( ( ))( ( ( ))(( ( ) ( ))()) ) (() ) ) ( ) ( ( ) ) ( ) ( )) ( ( ) ) ( ) ) ) ) ( ()) ) ( ( ) ) ( ) ( )) ( ) ) ( ( ((( ( ( (() ) )()())(()((()((()) ( ) ) ( ( ) ) ( ) ( ) ( ))( ) ( ( ( ) ( (((())
output:
impossible
result:
ok impossible
Test #20:
score: 0
Accepted
time: 0ms
memory: 3416kb
input:
100 ) ) ()))(((( ))() ( ( ( ) ( ) ( ( ) () ( ( ) ) ( ) ( ( ) ) ) ( ) ) ( ( ) ) ( ) ) ) ) ( ( ) (( ( ( ) ) ( ( ) ( ) (()(( ) ( ) ) (()))()()())))()()(( ( ) ) ( ( ( ) ) ( ( ) ( ( ( ) ( ( ) )( ( ) ) ) ( (())())(() ) ) ( () (( ( ) ) ) ) ( ) ( ( ) ) ( ()) )(
output:
51 41 86 70 53 57 60 61 62 65 66 68 69 5 72 73 76 80 84 87 92 94 95 98 47 6 7 9 11 12 15 16 19 21 22 26 29 30 33 38 39 42 43 46 49 14 85 75 81 100 3 56 48 45 44 40 37 36 35 34 32 31 1 27 25 24 23 20 18 17 13 10 8 2 28 99 97 96 93 91 90 89 88 83 82 50 78 77 74 71 67 64 63 59 58 55 54 52 79 4
result:
ok good plan
Test #21:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
100 ( ( ) ( ) ( ( ( ( ) ) ) ) () )( ) ) ( ( ) ( ( ) ) ) ( ) ( ( )))) ( ) ( ) ( ( ( ()()( ) ()) ( ( ) ) ( ( ) ( ( ) ) ( ( ( ( ( ) ( ( ((( ) ) ) )))) ( ))( ) ) () ())() ) ) ( ))) ( )((()))( ( ((( (( ( ) ( ( ) ( ) ) () )() ) ) ()))()( )(())( ) ( ( ( ( )( )
output:
78 60 79 75 48 49 52 53 54 55 56 58 59 65 73 2 77 80 82 83 85 95 96 97 98 26 6 7 4 8 9 1 18 19 21 46 22 28 29 31 33 35 36 37 38 41 42 45 69 14 88 99 93 15 76 92 66 50 47 44 43 40 39 34 32 27 3 24 23 20 17 16 13 12 11 10 5 25 100 94 91 90 89 87 86 84 81 51 71 70 68 67 63 62 61 57 72 74 30 64
result:
ok good plan
Test #22:
score: 0
Accepted
time: 1ms
memory: 3436kb
input:
1000 (())())()(((())()())(((()(()))((()((((()())))())))))(()(()((())(((()))()(() ) ( ) () ) )((())))) ) ((((((()))()())))))((()( (( ()(()())))(() )() ( (( ( ) ) )(() )))( ) )) ( (())))) )(())(((())(((( ) ) ( ( ())))(()) ((( ( ((( ())()( ()()) ) ) ) ( ))))())( ) ))( ) ())(()(()))))()(()((())((((()())...
output:
impossible
result:
ok impossible
Test #23:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
1000 ))(())) ( )))( ) (( ()))()))))()()( ))))((((((((()()(())((()() ( ) )()(() ( ()))))() ( (()(()(((()())(((((((())()()())())(())()))))((()((())((((((()(()() )(()())((())) ((( ) ) ( )(( ( ( ) ( ) ()(())((( ( ) ( ( ) ()(()(()()(()()((()))())((()())))))((())(((()()(())(()()())(()()(((())()(()((((((((...
output:
impossible
result:
ok impossible
Test #24:
score: 0
Accepted
time: 2ms
memory: 3584kb
input:
4000 ( ) )) )()))))( ( ) ( ) ) ) )((()(( ( ) )()( ) ) ) ) ( ) ( ) ) ( ()))((()))))()((()( ( ))) ( ) ( ( ( ( ) )()(()()(()()))))()) ) ) )((( ) ) ) ) ( ( ) ))()()))((()) ( ( ) ( ))( ( ) ) ( ) ) ())( ) ( ( ( ) ())))(())((()(()()((()(( ( ) ) ( ) ) ) ) ) ) ) ) ( ) (()))))( ) ) ( ())))(((())()( ( ( ()( ( ...
output:
impossible
result:
ok impossible
Test #25:
score: -100
Wrong Answer
time: 27ms
memory: 5580kb
input:
1000000 ) ( )()(((()))( ( ( ( ) ( ( ) ) (((())((()(()((()) ( ) )( ) ) ))))(()))()())(()((()))(()()()))()()()))))))))(())))((((()(()()))((((((()((((()()( ) (( ) ) ( ) ())()()(( ) )))(())((()))((()()))(()(())())))())))())))(()()( ( ()( ( ( ()() ) )) ) ( ( ( ) ) ) ( ) ( ) ) ) )(()))())) ( ) ))) ( ) ( (...
output:
impossible
result:
wrong answer you didn't find a solution but jury did