QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#69231 | #5108. Prehistoric Programs | rivalq | WA | 8ms | 5292kb | C++14 | 2.3kb | 2022-12-25 17:44:05 | 2022-12-25 17:44:07 |
Judging History
answer
// Jai Shree Ram
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ll long long
#define int long long
#define pb push_back
#define all(v) v.begin(),v.end()
#define endl "\n"
#define x first
#define y second
#define gcd(a,b) __gcd(a,b)
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define hell 1000000007
#define elasped_time 1.0 * clock() / CLOCKS_PER_SEC
template<typename T1,typename T2>istream& operator>>(istream& in,pair<T1,T2> &a){in>>a.x>>a.y;return in;}
template<typename T1,typename T2>ostream& operator<<(ostream& out,pair<T1,T2> a){out<<a.x<<" "<<a.y;return out;}
template<typename T,typename T1>T maxs(T &a,T1 b){if(b>a)a=b;return a;}
template<typename T,typename T1>T mins(T &a,T1 b){if(b<a)a=b;return a;}
int solve(){
int n; cin >> n;
vector<pair<int,pii>> vec1, vec2;
for(int i = 0; i < n; i++){
string s; cin >> s;
int bal = 0, mn = 0;
for(auto j: s){
if(j == '(') bal++;
else bal--;
mins(mn,bal);
}
if(bal > 0){
vec1.push_back({i,{bal,mn}});
}else{
vec2.push_back({i,{bal,mn}});
}
}
sort(all(vec1),[&](auto &a, auto &b){
return a.y.y > b.y.y;
});
sort(all(vec2),[&](auto &a, auto &b){
return a.y.y < b.y.y;
});
int sum = 0;
vector<int> ans;
for(auto [i,p]: vec1){
auto [bal,mn] = p;
if(sum + mn < 0){
cout << "impossible" << endl;
return 0;
}
ans.push_back(i + 1);
sum += bal;
}
for(auto [i,p]: vec2){
auto [bal,mn] = p;
if(sum + mn < 0){
cout << "impossible" << endl;
return 0;
}
ans.push_back(i + 1);
sum += bal;
}
if(sum != 0){
cout << "impossible" << endl;
return 0;
}
for(auto i: ans) cout << i << endl;
return 0;
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
#ifdef SIEVE
sieve();
#endif
#ifdef NCR
init();
#endif
int t=1;//cin>>t;
while(t--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 5292kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
32265 32296 32293 32292 32290 32287 32281 32280 32276 32274 32266 32297 32264 32255 32254 32253 32252 32251 32250 32248 32245 32243 32329 32350 32347 32345 32344 32343 32338 32337 32336 32333 32331 32242 32326 32324 32316 32314 32310 32308 32306 32302 32301 32170 32188 32187 32185 32184 32183 32182 ...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 2ms
memory: 3480kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
561 584 577 576 575 573 570 566 564 563 562 585 560 557 554 553 544 535 534 524 522 636 666 663 662 659 655 652 650 646 640 638 517 632 628 619 615 611 604 598 595 590 399 439 430 427 426 422 420 414 410 408 406 443 398 396 390 387 386 384 382 381 379 471 516 514 511 502 498 496 481 476 474 473 667 ...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 2ms
memory: 3336kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 2ms
memory: 3296kb
input:
3 () ( )
output:
2 3 1
result:
ok good plan
Test #7:
score: 0
Accepted
time: 2ms
memory: 3296kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 2ms
memory: 3408kb
input:
5 ))( (() )( ( )
output:
2 4 1 3 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 2ms
memory: 3452kb
input:
3 (( ))()) (
output:
1 3 2
result:
ok good plan
Test #10:
score: 0
Accepted
time: 2ms
memory: 3404kb
input:
6 ) () ()()() (( ) )
output:
impossible
result:
ok impossible
Test #11:
score: 0
Accepted
time: 2ms
memory: 3488kb
input:
500 ( ) ) ( )( ( ( ) ))( ( ( ( ( ) ) ( ( ) ( ( ) ( ()(() ( )()) ( ( ) ( )()(( ( ) ( ) ) ( ( ( ) ( ( ) ) )( ( ( ) ) ( ) ( ( ( ) ( ( ()))) ( ( ( ) ( ) ) ( ( ) ) ( ( ( ( ( () ( ( ( ( ( (( ) ( ( ) ( ( ( ) ()) ( ( ( ) ( ( ( ) ) ( ) ) ( ) ( ( ( ( ) ( ) ) ) ) ( ) )))()( ( ) ) ( ) )( ) ( ) ) )) ( ( ( ( ( ( ...
output:
334 290 296 297 308 309 311 315 318 320 321 325 327 329 330 288 338 339 340 343 344 345 349 350 351 353 356 357 360 362 262 234 1 240 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 439 440 442 443 445 449 452 456 459 464 43...
result:
ok good plan
Test #12:
score: 0
Accepted
time: 0ms
memory: 3312kb
input:
50 ) ) ((((()())())))(())(()) ()(((())) (((()))(() ()((( )) ) )()))(()(()())(((((() ( ) ) )(( )()(( ())())) (())))() ((( ))))(() ()(())(()))())() ) ) ( ( ( ( ((())()())())))(((()) ()( (()(())()((() ()(((()())))())()( ) )((() ( ) (( ) ()( ( ( ) )))((()) ) ()))()(((()(() (( ((()))(())(()())(()())())()...
output:
5 43 38 37 36 34 32 28 27 25 24 23 22 17 10 6 4 31 14 13 46 42 9 45 44 50 49 18 26 40 15 16 19 48 47 7 2 8 41 11 39 35 33 30 29 1 21 20 12 3
result:
ok good plan
Test #13:
score: -100
Wrong Answer
time: 0ms
memory: 3376kb
input:
50 ) ( )()( ())( ()()(((((())( )(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...
output:
impossible
result:
wrong answer you didn't find a solution but jury did