QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#69229 | #5108. Prehistoric Programs | rivalq | WA | 6ms | 5176kb | C++14 | 2.2kb | 2022-12-25 17:37:53 | 2022-12-25 17:37:55 |
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>> vec;
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);
}
vec.push_back({i,{bal,mn}});
}
sort(all(vec),[&](auto &a, auto &b){
if(a.y.x > 0 and b.y.x <= 0) return true;
if(a.y.x <= 0 and b.y.x > 0) return false;
if(a.y.x > 0 and b.y.x > 0) return a.y.y > b.y.y;
return a.y.y < b.y.y;
});
int sum = 0;
vector<int> ans;
for(auto [i,p]: vec){
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: 6ms
memory: 5176kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
26315 26345 26341 26339 26336 26334 26333 26329 26328 26327 26321 26320 26318 26317 26316 26347 26313 26311 26308 26307 26305 26302 26297 26295 26294 26292 26290 26289 26286 26384 26414 26413 26412 26409 26406 26402 26401 26399 26398 26396 26395 26394 26393 26285 26383 26382 26380 26376 26370 26366 ...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 3ms
memory: 3508kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
252 267 573 265 799 859 258 257 929 575 253 268 640 576 933 247 707 245 243 242 934 239 287 915 803 301 863 919 296 481 291 290 570 798 286 801 282 925 280 554 553 271 819 945 820 619 198 943 584 793 854 190 189 188 719 585 725 182 181 947 179 178 177 948 638 715 935 577 496 498 711 857 229 228 502 ...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 2ms
memory: 3296kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 2ms
memory: 3456kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 2ms
memory: 3300kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 2ms
memory: 3364kb
input:
3 () ( )
output:
2 3 1
result:
ok good plan
Test #7:
score: 0
Accepted
time: 2ms
memory: 3336kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 2ms
memory: 3352kb
input:
5 ))( (() )( ( )
output:
2 4 1 3 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 2ms
memory: 3344kb
input:
3 (( ))()) (
output:
1 3 2
result:
ok good plan
Test #10:
score: 0
Accepted
time: 2ms
memory: 3284kb
input:
6 ) () ()()() (( ) )
output:
impossible
result:
ok impossible
Test #11:
score: 0
Accepted
time: 2ms
memory: 3308kb
input:
500 ( ) ) ( )( ( ( ) ))( ( ( ( ( ) ) ( ( ) ( ( ) ( ()(() ( )()) ( ( ) ( )()(( ( ) ( ) ) ( ( ( ) ( ( ) ) )( ( ( ) ) ( ) ( ( ( ) ( ( ()))) ( ( ( ) ( ) ) ( ( ) ) ( ( ( ( ( () ( ( ( ( ( (( ) ( ( ) ( ( ( ) ()) ( ( ( ) ( ( ( ) ) ( ) ) ( ) ( ( ( ( ) ( ) ) ) ) ( ) )))()( ( ) ) ( ) )( ) ( ) ) )) ( ( ( ( ( ( ...
output:
415 209 208 207 412 205 413 203 414 210 416 199 198 196 194 192 191 420 405 395 232 398 228 227 226 399 404 186 219 406 409 214 410 411 211 153 437 160 159 158 157 156 439 440 436 152 442 149 443 445 143 141 427 184 424 182 180 426 178 177 176 234 428 171 429 431 166 434 435 362 318 315 356 357 311 ...
result:
ok good plan
Test #12:
score: -100
Wrong Answer
time: 2ms
memory: 3288kb
input:
50 ) ) ((((()())())))(())(()) ()(((())) (((()))(() ()((( )) ) )()))(()(()())(((((() ( ) ) )(( )()(( ())())) (())))() ((( ))))(() ()(())(()))())() ) ) ( ( ( ( ((())()())())))(((()) ()( (()(())()((() ()(((()())))())()( ) )((() ( ) (( ) ()( ( ( ) )))((()) ) ()))()(((()(() (( ((()))(())(()())(()())())()...
output:
impossible
result:
wrong answer you didn't find a solution but jury did