QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #355126 | #5108. Prehistoric Programs | ucup-team052# | WA | 14ms | 36388kb | C++23 | 1.1kb | 2024-03-16 13:40:26 | 2024-03-16 13:40:27 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
string s[N];
int mn[N],sum[N],id[N],vis[N];
int n;
signed main()
{
#ifdef xay5421
freopen("a.in","r",stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=1;i<=n;i++)
{
int l=s[i].length();
int cur=0;
for(int j=0;j<l;j++)
{
if(s[i][j]=='(') cur++;
else cur--;
mn[i]=min(mn[i],cur);
}
sum[i]=cur;
id[i]=i;
}
// for(int i=1;i<=n;i++) printf("%d %d\n",mn[i],sum[i]);
sort(id+1,id+n+1,[&](int x,int y){return mn[x]>mn[y];});
vector<int> ans;
int cur=0;
for(int i=1;i<=n;i++)
{
int u=id[i];
if(mn[u]+cur>=0&&sum[u]>=0)
{
vis[u]=1,ans.push_back(u);
cur+=sum[u];
}
}
sort(id+1,id+n+1,[&](int x,int y){return -sum[x]-mn[x]>-sum[y]-mn[y];});
for(int i=1;i<=n;i++)
{
int u=id[i];
if(!vis[u]&&mn[u]+cur>=0)
{
cur+=sum[u];
ans.push_back(u);
vis[u]=1;
}
}
if((int)ans.size()!=n) printf("impossible\n");
else
{
for(int i:ans) printf("%d\n",i);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 14ms
memory: 36388kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
26700 26740 26738 26737 26729 26727 26724 26723 26716 26715 26714 26713 26711 26709 26703 26744 26698 26696 26695 26693 26692 26689 26685 26682 26679 26677 26674 26672 26671 26670 26779 26819 26817 26815 26813 26810 26809 26806 26803 26802 26800 26792 26787 26784 26783 26668 26778 26777 26776 26773 ...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 7ms
memory: 35156kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
715 296 687 689 291 290 287 286 282 280 707 711 297 271 719 268 267 265 725 731 732 738 258 316 650 652 329 653 327 655 324 659 662 663 666 257 667 668 313 673 309 680 681 301 685 686 790 779 217 216 215 214 213 212 209 208 206 788 778 198 197 793 798 799 190 189 188 801 803 757 253 252 746 747 748 ...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 7ms
memory: 35028kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 3ms
memory: 34956kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 3ms
memory: 35120kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 9ms
memory: 35060kb
input:
3 () ( )
output:
1 2 3
result:
ok good plan
Test #7:
score: 0
Accepted
time: 4ms
memory: 34992kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 7ms
memory: 34956kb
input:
5 ))( (() )( ( )
output:
2 4 3 1 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 7ms
memory: 35248kb
input:
3 (( ))()) (
output:
1 3 2
result:
ok good plan
Test #10:
score: 0
Accepted
time: 0ms
memory: 35160kb
input:
6 ) () ()()() (( ) )
output:
impossible
result:
ok impossible
Test #11:
score: 0
Accepted
time: 0ms
memory: 35040kb
input:
500 ( ) ) ( )( ( ( ) ))( ( ( ( ( ) ) ( ( ) ( ( ) ( ()(() ( )()) ( ( ) ( )()(( ( ) ( ) ) ( ( ( ) ( ( ) ) )( ( ( ) ) ( ) ( ( ( ) ( ( ()))) ( ( ( ) ( ) ) ( ( ) ) ( ( ( ( ( () ( ( ( ( ( (( ) ( ( ) ( ( ( ) ()) ( ( ( ) ( ( ( ) ) ( ) ) ( ) ( ( ( ( ) ( ) ) ) ) ( ) )))()( ( ) ) ( ) )( ) ( ) ) )) ( ( ( ( ( ( ...
output:
194 204 203 404 405 406 199 198 196 205 409 192 191 410 411 412 413 186 399 228 227 226 392 393 395 219 398 414 214 401 211 210 209 208 207 149 160 159 158 157 156 431 153 152 429 434 435 436 437 438 143 439 141 420 184 415 182 416 180 178 177 176 388 172 171 424 166 426 427 428 353 304 345 348 349 ...
result:
ok good plan
Test #12:
score: 0
Accepted
time: 0ms
memory: 35216kb
input:
50 ) ) ((((()())())))(())(()) ()(((())) (((()))(() ()((( )) ) )()))(()(()())(((((() ( ) ) )(( )()(( ())())) (())))() ((( ))))(() ()(())(()))())() ) ) ( ( ( ( ((())()())())))(((()) ()( (()(())()((() ()(((()())))())()( ) )((() ( ) (( ) ()( ( ( ) )))((()) ) ()))()(((()(() (( ((()))(())(()())(()())())()...
output:
34 27 25 24 23 22 28 17 32 36 37 10 38 43 6 5 4 3 31 29 46 14 13 42 9 45 44 50 49 18 15 40 48 19 16 7 26 47 41 8 11 12 20 21 1 30 33 39 2 35
result:
ok good plan
Test #13:
score: 0
Accepted
time: 7ms
memory: 35288kb
input:
50 ) ( )()( ())( ()()(((((())( )(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...
output:
2 47 46 41 40 33 28 26 18 16 15 13 11 8 5 37 4 42 44 3 10 19 29 21 6 31 36 12 17 39 23 49 50 48 1 24 45 14 32 9 38 35 34 43 20 22 25 27 7 30
result:
ok good plan
Test #14:
score: 0
Accepted
time: 10ms
memory: 35756kb
input:
150 ))(()))(())(())))()))())()()()(())(((())))()))))() )))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...
output:
111 32 136 35 37 38 40 130 48 49 52 53 120 60 149 69 106 73 105 104 79 103 84 100 87 98 92 94 14 143 12 20 142 11 17 7 6 4 24 141 140 15 148 28 10 70 62 5 89 91 93 96 51 133 23 129 135 27 117 137 16 61 102 147 77 29 125 122 2 3 9 25 115 56 47 43 41 18 86 134 150 59 85 30 45 19 55 72 71 127 81 116 50...
result:
ok good plan
Test #15:
score: 0
Accepted
time: 3ms
memory: 36164kb
input:
150 )))( (() (())((())))(()))()(() ((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()()))))) ( ...
output:
87 36 37 42 44 46 49 51 52 56 58 61 64 66 70 86 2 89 94 98 100 104 118 121 127 128 129 141 142 148 149 150 10 26 5 19 15 8 4 32 14 16 117 75 113 112 80 107 84 18 145 29 102 50 55 23 114 34 136 82 74 76 63 39 53 88 90 144 85 21 140 13 7 41 62 45 122 81 96 40 79 111 12 125 97 123 116 22 115 108 138 12...
result:
ok good plan
Test #16:
score: 0
Accepted
time: 3ms
memory: 35644kb
input:
150 )()(( ) )))()))) )()())((()(()())((())()))(()))(())((((((((()()(())())(()(((()))())()((()((())())))))))()((()))))((()(((()(((((()))()))((()((()()))(())))))()))))()())()()())(())(())(()))())((((((()()()))()((((()))))))((())()))()(()((()(())(())(())()())(()) ()() ) (())()))(())(()((())()()())())((...
output:
118 68 67 30 65 106 123 122 36 108 60 27 110 117 115 45 58 48 50 111 52 55 84 93 81 8 92 140 97 99 136 98 131 75 130 129 74 5 89 149 56 57 63 1 88 70 100 11 9 19 127 24 26 31 124 42 46 91 146 128 101 120 119 114 35 15 14 82 37 133 107 43 32 90 12 78 44 112 61 7 64 109 125 134 72 85 71 77 95 116 20 1...
result:
ok good plan
Test #17:
score: 0
Accepted
time: 4ms
memory: 35336kb
input:
750 (()()((()((((())()((()))()()))()))(()()(()))(()(())()))(((((( ))))))) ) ((()()()(())((()(()())(())(((()((((()))(()(())((())(()())(())())))())))()(())()))((()(()((((()(()))(()())()((()()()))))(())())(())())())()((()( ) ) ( )()(((()(())))()))))(((((((()))()()()(()())))(()())(()(( ( ) )(())) ((())(...
output:
228 246 243 541 238 547 549 231 230 229 530 227 554 225 224 555 556 220 218 563 512 500 276 502 274 504 269 265 264 263 214 516 518 259 258 522 255 526 252 250 594 186 185 184 591 182 181 180 592 593 590 176 175 172 169 601 166 164 163 162 574 213 212 569 208 570 571 572 204 573 281 197 581 195 584 ...
result:
ok good plan
Test #18:
score: 0
Accepted
time: 3ms
memory: 35432kb
input:
100 ) ) ) ( ) ( ))))() ) ( ( ( ( ) ) ) ) ( ( ( ( ()) ( ) ) )(( ) ( ( ( ) ( ( ) ) ) ) ()(( ( ) ) ) )((( (((( ( ) ( ) (( ) ( ( ) ( ())(())) ) ) ( ) ( ( ( ( )))()() ) ( ( ( ( ) ( ) ) ) ( ) ) ) ) ( ) ( ( ) ( ) ( ( ( ) ) ( ) ) ( )(((( ) ) ()((()()(())))) ) (
output:
66 32 37 38 43 44 46 48 50 53 57 59 60 61 62 65 51 67 68 70 74 79 81 82 84 86 87 88 91 94 100 28 10 9 11 22 6 20 19 4 27 18 17 29 31 12 95 42 25 7 63 54 34 77 33 69 2 99 98 97 96 3 93 92 90 89 5 85 16 83 80 71 72 73 78 1 13 14 15 64 21 58 56 55 23 52 35 24 49 47 26 45 41 40 39 30 36 76 75 8
result:
ok good plan
Test #19:
score: -100
Wrong Answer
time: 3ms
memory: 36020kb
input:
100 ) ()( ( ) ( ) ( ( ) ) )(() ) ))) ) ) ( ( ( ) ( ( ) ( ) ( ( ( ))( ( ( ))(( ( ) ( ))()) ) (() ) ) ( ) ( ( ) ) ( ) ( )) ( ( ) ) ( ) ) ) ) ( ()) ) ( ( ) ) ( ) ( )) ( ) ) ( ( ((( ( ( (() ) )()())(()((()((()) ( ) ) ( ( ) ) ( ) ( ) ( ))( ) ( ( ( ) ( (((())
output:
50 73 70 68 66 63 62 59 54 74 48 46 43 42 40 37 34 51 75 76 77 78 81 84 85 88 90 92 95 96 97 99 100 2 25 23 16 26 17 27 8 21 7 18 29 30 20 5 32 3 11 31 80 35 13 49 69 28 93 87 44 9 89 91 94 6 4 98 57 67 86 10 83 82 12 79 14 71 15 72 24 19 33 65 64 22 61 36 60 38 41 58 56 55 53 52 1 39 47 45
result:
wrong answer wrong plan (expected impossible)