QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69231#5108. Prehistoric ProgramsrivalqWA 8ms5292kbC++142.3kb2022-12-25 17:44:052022-12-25 17:44:07

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-12-25 17:44:07]
  • 评测
  • 测评结果:WA
  • 用时:8ms
  • 内存:5292kb
  • [2022-12-25 17:44:05]
  • 提交

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