QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66050 | #5108. Prehistoric Programs | rumen_m# | WA | 1087ms | 5676kb | C++14 | 1.3kb | 2022-12-06 02:26:42 | 2022-12-06 02:26:45 |
Judging History
answer
# include <bits/stdc++.h>
const long long MAXN = 1e6+5;
using namespace std;
struct ww
{
int id;
int ends;
int nms;
};
ww seq[MAXN];
bool cmp(ww i, ww j)
{
if(i.nms >= 0)
{
if( j.nms < 0) return true;
return i.ends >= j.ends;
}
if(j.nms >= 0) return false;
if(i.ends > 0)
{
if(j.ends <= 0) return true;
return i.ends <= j.ends;
}
if(j.ends > 0) return false;
return i.nms >= j.nms;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
string s;
int i,j;
cin>>n;
for(i = 1; i <= n; i++)
{
cin>>s;
seq[i].id= i;
seq[i].nms = 0;
seq[i].ends = 0;
for(char ch:s)
{
if(ch=='(')
{
seq[i].ends++;
}else
seq[i].ends--;
seq[i].nms = min(seq[i].nms,seq[i].ends);
}
}
sort(seq+1,seq+n+1,cmp);
int currD=0;
for(i =1; i <= n; i++)
{
if(currD - seq[i].nms < 0){cout<<"impossible\n";return 0;}
currD+=seq[i].ends;
}
if(currD!=0){cout<<"impossible\n";return 0;}
for(i = 1; i <=n; i++)
cout<<seq[i].id<<endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1087ms
memory: 5676kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
41248 4238 13809 5338 27609 48374 389 2458 48749 6754 42979 18533 14096 6986 31692 32583 5803 23456 3405 169 10427 26695 43508 26677 38930 9225 34539 2253 46429 11398 41740 25061 24373 35132 39743 30771 46194 21764 5699 31402 33777 45491 35039 34110 23312 35743 41641 41639 463 7365 9790 6701 23551 3...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 11ms
memory: 3452kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
36 13 66 386 966 585 286 257 83 127 39 476 595 329 907 814 214 598 62 427 981 707 662 384 131 511 807 793 638 869 449 80 271 767 379 422 746 387 327 239 474 632 20 553 171 915 919 334 535 345 296 989 168 975 31 715 473 502 88 390 947 98 17 725 464 177 686 164 604 945 316 827 881 852 819 406 134 258 ...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 2ms
memory: 3420kb
input:
2 () ()
output:
2 1
result:
ok good plan
Test #4:
score: 0
Accepted
time: 2ms
memory: 3220kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: -100
Wrong Answer
time: 2ms
memory: 3376kb
input:
2 )( ()
output:
2 1
result:
wrong answer wrong plan (expected impossible)