QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#69230#5108. Prehistoric ProgramsrivalqWA 196ms46520kbC++142.3kb2022-12-25 17:42:492022-12-25 17:42:49

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:42:49]
  • 评测
  • 测评结果:WA
  • 用时:196ms
  • 内存:46520kb
  • [2022-12-25 17:42:49]
  • 提交

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;
}
 

詳細信息

Test #1:

score: 100
Accepted
time: 4ms
memory: 5252kb

input:

50000
(
(
))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()(
)
(
)
(((
(
(
(
(
(
()
(
)
(
)((())()((
)))))(
(
)
))
)()
(
)
)
)()(
(
(
()
(
)
(
)()((((())()))())(
(
(
)(
(
(
(()())())
)
)
(
(
(
)((())))((())))))))))((((()()))()))))))))((()())()))
)
)()
)
)
)
)
)
())(())))))()(()((()(())...

output:

31744
31767
31765
31764
31763
31759
31757
31755
31754
31753
31750
31747
31768
31743
31740
31738
31736
31734
31727
31726
31722
31721
31711
31710
31796
31818
31817
31815
31814
31812
31809
31806
31803
31801
31799
31798
31705
31795
31794
31793
31789
31787
31785
31784
31782
31777
31775
31634
31658
31656
...

result:

ok good plan

Test #2:

score: 0
Accepted
time: 3ms
memory: 3428kb

input:

1000
(
))(()))
((((())())))((())(()))(
)(
)
)))
))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()())
)((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))(
)))(((
(
)))()()())))
(
(((())(((...

output:

554
576
575
573
570
566
564
563
562
561
560
557
577
553
544
535
534
524
522
517
516
514
511
502
619
655
653
652
650
646
640
638
636
632
628
626
498
617
615
611
604
598
596
595
590
585
584
387
422
420
414
410
408
406
399
398
397
396
390
426
386
384
382
381
379
377
372
371
356
347
345
460
496
489
481
...

result:

ok good plan

Test #3:

score: 0
Accepted
time: 1ms
memory: 3288kb

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

score: 0
Accepted
time: 0ms
memory: 3280kb

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

score: 0
Accepted
time: 1ms
memory: 3340kb

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

score: 0
Accepted
time: 2ms
memory: 3304kb

input:

3
()
(
)

output:

1
2
3

result:

ok good plan

Test #7:

score: 0
Accepted
time: 2ms
memory: 3396kb

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

score: 0
Accepted
time: 2ms
memory: 3284kb

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5

result:

ok good plan

Test #9:

score: 0
Accepted
time: 2ms
memory: 3348kb

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

score: 0
Accepted
time: 0ms
memory: 3444kb

input:

6
)
()
()()()
((
)
)

output:

impossible

result:

ok impossible

Test #11:

score: 0
Accepted
time: 2ms
memory: 3496kb

input:

500
(
)
)
(
)(
(
(
)
))(
(
(
(
(
)
)
(
(
)
(
(
)
(
()(()
(
)())
(
(
)
(
)()((
(
)
(
)
)
(
(
(
)
(
(
)
)
)(
(
(
)
)
(
)
(
(
(
)
(
(
())))
(
(
(
)
(
)
)
(
(
)
)
(
(
(
(
(
()
(
(
(
(
(
((
)
(
(
)
(
(
(
)
())
(
(
(
)
(
(
(
)
)
(
)
)
(
)
(
(
(
(
)
(
)
)
)
)
(
)
)))()(
(
)
)
(
)
)(
)
(
)
)
))
(
(
(
(
(
(
...

output:

334
290
296
297
304
308
309
311
315
318
320
321
325
327
329
330
288
338
339
340
343
344
345
348
349
350
351
353
356
357
360
362
262
232
234
239
1
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
438
439
440
442
443
445
449
45...

result:

ok good plan

Test #12:

score: 0
Accepted
time: 2ms
memory: 3312kb

input:

50
)
)
((((()())())))(())(())
()(((()))
(((()))(()
()(((
))
)
)()))(()(()())(((((()
(
)
)
)((
)()((
())()))
(())))()
(((
))))(()
()(())(()))())()
)
)
(
(
(
(
((())()())())))(((())
()(
(()(())()((()
()(((()())))())()(
)
)((()
(
)
((
)
()(
(
(
)
)))((())
)
()))()(((()(()
((
((()))(())(()())(()())())()...

output:

4
43
38
37
36
34
32
28
27
25
24
23
22
17
10
6
5
3
14
29
31
13
46
42
9
45
44
50
49
18
26
40
15
19
16
7
48
47
2
8
11
41
12
39
35
33
30
1
21
20

result:

ok good plan

Test #13:

score: 0
Accepted
time: 2ms
memory: 3472kb

input:

50
)
(
)()(
())(
()()(((((())(
)(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...

output:

15
33
40
28
26
41
2
18
16
13
11
8
5
46
47
19
42
44
37
10
4
3
29
21
6
31
12
36
17
23
39
30
50
49
48
45
43
38
35
34
32
1
27
25
24
22
20
14
9
7

result:

ok good plan

Test #14:

score: 0
Accepted
time: 3ms
memory: 3392kb

input:

150
))(()))(())(())))()))())()()()(())(((())))()))))()
)))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...

output:

79
38
40
140
136
48
49
52
53
130
60
69
73
149
84
87
92
94
98
100
103
104
105
106
111
120
148
15
17
14
143
12
20
11
24
142
7
6
28
4
37
141
32
35
117
10
5
96
93
91
89
23
137
135
27
51
133
129
61
62
70
16
102
147
77
29
122
3
125
2
9
25
86
18
41
43
47
56
115
134
150
59
45
30
85
19
55
72
21
71
127
50
116...

result:

ok good plan

Test #15:

score: 0
Accepted
time: 2ms
memory: 3312kb

input:

150
)))(
(()
(())((())))(()))()(()
((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()())))))
(
...

output:

98
51
52
56
58
61
64
2
70
86
87
89
94
66
100
104
118
121
127
128
129
141
142
148
149
150
37
26
32
19
36
15
14
10
42
49
46
4
5
44
8
50
16
18
117
113
112
107
145
102
23
29
55
84
80
75
74
53
136
63
39
76
114
82
34
90
88
85
144
21
13
140
41
7
62
45
122
40
81
96
111
79
97
12
125
116
123
22
108
20
139
115...

result:

ok good plan

Test #16:

score: 0
Accepted
time: 2ms
memory: 3484kb

input:

150
)()((
)
)))())))
)()())((()(()())((())()))(()))(())((((((((()()(())())(()(((()))())()((()((())())))))))()((()))))((()(((()(((((()))()))((()((()()))(())))))()))))()())()()())(())(())(()))())((((((()()()))()((((()))))))((())()))()(()((()(())(())(())()())(())
()()
)
(())()))(())(()((())()()())())((...

output:

106
60
65
67
68
74
75
81
84
89
92
93
97
98
99
5
108
110
111
115
117
118
122
123
129
130
131
136
140
149
48
36
30
27
45
50
52
55
8
58
127
11
57
124
19
24
9
26
1
31
100
42
63
56
70
46
88
119
146
128
14
15
120
82
114
35
91
101
37
107
133
43
32
90
78
12
44
61
112
7
64
109
125
72
134
85
71
77
95
20
116
1...

result:

ok good plan

Test #17:

score: 0
Accepted
time: 3ms
memory: 3432kb

input:

750
(()()((()((((())()((()))()()))()))(()()(()))(()(())()))((((((
)))))))
)
((()()()(())((()(()())(())(((()((((()))(()(())((())(()())(())())))())))()(())()))((()(()((((()(()))(()())()((()()()))))(())())(())())())()((()(
)
)
(
)()(((()(())))()))))(((((((()))()()()(()())))(()())(()((
(
)
)(()))
((())(...

output:

437
470
469
468
461
455
450
446
442
441
440
473
434
432
429
427
426
425
419
418
417
495
530
526
522
518
516
512
504
502
500
414
494
492
491
490
489
485
481
477
475
348
378
374
371
369
368
362
361
360
358
357
379
345
343
341
338
335
333
332
331
330
395
409
408
407
406
405
401
400
397
396
541
394
392
...

result:

ok good plan

Test #18:

score: 0
Accepted
time: 2ms
memory: 3284kb

input:

100
)
)
)
(
)
(
))))()
)
(
(
(
(
)
)
)
)
(
(
(
(
())
(
)
)
)((
)
(
(
(
)
(
(
)
)
)
)
()((
(
)
)
)
)(((
((((
(
)
(
)
((
)
(
(
)
(
())(()))
)
)
(
)
(
(
(
(
)))()()
)
(
(
(
(
)
(
)
)
)
(
)
)
)
)
(
)
(
(
)
(
)
(
(
(
)
)
(
)
)
(
)((((
)
)
()((()()(()))))
)
(

output:

70
51
53
57
59
60
61
62
65
66
67
68
50
74
79
81
82
84
86
87
88
91
94
100
27
6
9
10
11
12
17
18
19
20
22
4
28
29
31
32
37
38
43
44
46
48
25
42
95
7
63
54
78
55
56
58
64
69
71
72
73
75
76
77
52
80
83
85
89
90
92
93
96
97
98
99
26
2
3
5
8
13
14
15
16
21
23
24
1
30
33
34
35
36
39
40
41
45
47
49

result:

ok good plan

Test #19:

score: 0
Accepted
time: 2ms
memory: 3304kb

input:

100
)
()(
(
)
(
)
(
(
)
)
)(()
)
)))
)
)
(
(
(
)
(
(
)
(
)
(
(
(
))(
(
(
))((
(
)
(
))())
)
(()
)
)
(
)
(
(
)
)
(
)
(
))
(
(
)
)
(
)
)
)
)
(
())
)
(
(
)
)
(
)
(
))
(
)
)
(
(
(((
(
(
(()
)
)()())(()((()((())
(
)
)
(
(
)
)
(
)
(
)
(
))(
)
(
(
(
)
(
(((())

output:

impossible

result:

ok impossible

Test #20:

score: 0
Accepted
time: 2ms
memory: 3288kb

input:

100
)
)
()))((((
))()
(
(
(
)
(
)
(
(
)
()
(
(
)
)
(
)
(
(
)
)
)
(
)
)
(
(
)
)
(
)
)
)
)
(
(
)
((
(
(
)
)
(
(
)
(
)
(()((
)
(
)
)
(()))()()())))()()((
(
)
)
(
(
(
)
)
(
(
)
(
(
(
)
(
(
)
)(
(
)
)
)
(
(())())(()
)
)
(
()
((
(
)
)
)
)
(
)
(
(
)
)
(
())
)(

output:

72
51
53
57
60
61
62
65
66
68
69
70
5
73
76
80
84
85
86
87
92
94
95
98
47
6
7
9
11
12
14
15
16
19
21
22
26
29
30
33
38
39
41
42
43
46
49
75
81
100
3
56
4
79
54
55
58
59
63
64
67
71
74
77
78
50
82
83
88
89
90
91
93
96
97
99
28
2
8
10
13
17
18
20
23
24
25
27
52
31
32
34
35
36
37
40
44
45
48
1

result:

ok good plan

Test #21:

score: 0
Accepted
time: 2ms
memory: 3364kb

input:

100
(
(
)
(
)
(
(
(
(
)
)
)
)
()
)(
)
)
(
(
)
(
(
)
)
)
(
)
(
(
))))
(
)
(
)
(
(
(
()()(
)
())
(
(
)
)
(
(
)
(
(
)
)
(
(
(
(
(
)
(
(
(((
)
)
)
))))
(
))(
)
)
()
())()
)
)
(
)))
(
)((()))(
(
(((
((
(
)
(
(
)
(
)
)
()
)()
)
)
()))()(
)(())(
)
(
(
(
(
)(
)

output:

75
49
52
53
54
55
56
58
59
60
65
69
73
2
77
78
79
80
82
83
85
88
95
96
97
98
26
6
7
4
8
9
14
1
18
19
21
22
48
28
29
31
33
35
36
37
38
41
42
45
46
99
93
15
76
64
30
74
92
66
61
51
62
63
67
68
70
71
72
81
84
86
87
89
90
91
94
100
25
5
10
11
12
13
16
17
20
23
24
57
27
32
34
39
40
43
44
47
50
3

result:

ok good plan

Test #22:

score: 0
Accepted
time: 1ms
memory: 3412kb

input:

1000
(())())()(((())()())(((()(()))((()((((()())))())))))(()(()((())(((()))()(()
)
(
)
()
)
)((()))))
)
((((((()))()())))))((()(
((
()(()())))(()
)()
(
((
(
)
)
)(()
)))(
)
))
(
(()))))
)(())(((())((((
)
)
(
(
())))(())
(((
(
(((
())()(
()())
)
)
)
(
))))())(
)
))(
)
())(()(()))))()(()((())((((()())...

output:

impossible

result:

ok impossible

Test #23:

score: 0
Accepted
time: 3ms
memory: 3380kb

input:

1000
))(()))
(
)))(
)
((
()))()))))()()(
))))((((((((()()(())((()()
(
)
)()(()
(
()))))()
(
(()(()(((()())(((((((())()()())())(())()))))((()((())((((((()(()()
)(()())((()))
(((
)
)
(
)((
(
(
)
(
)
()(())(((
(
)
(
(
)
()(()(()()(()()((()))())((()())))))((())(((()()(())(()()())(()()(((())()(()((((((((...

output:

impossible

result:

ok impossible

Test #24:

score: 0
Accepted
time: 3ms
memory: 3436kb

input:

4000
(
)
))
)()))))(
(
)
(
)
)
)
)((()((
(
)
)()(
)
)
)
)
(
)
(
)
)
(
()))((()))))()((()(
(
)))
(
)
(
(
(
(
)
)()(()()(()()))))())
)
)
)(((
)
)
)
)
(
(
)
))()()))((())
(
(
)
(
))(
(
)
)
(
)
)
())(
)
(
(
(
)
())))(())((()(()()((()((
(
)
)
(
)
)
)
)
)
)
)
)
(
)
(()))))(
)
)
(
())))(((())()(
(
(
()(
(
...

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 176ms
memory: 42424kb

input:

1000000
)
(
)()(((()))(
(
(
(
)
(
(
)
)
(((())((()(()((())
(
)
)(
)
)
))))(()))()())(()((()))(()()()))()()()))))))))(())))((((()(()()))((((((()((((()()(
)
((
)
)
(
)
())()()((
)
)))(())((()))((()()))(()(())())))())))())))(()()(
(
()(
(
(
()()
)
))
)
(
(
(
)
)
)
(
)
(
)
)
)
)(()))()))
(
)
)))
(
)
(
(...

output:

641462
641493
641489
641488
641485
641484
641480
641479
641476
641474
641473
641471
641469
641465
641464
641494
641461
641460
641459
641456
641454
641453
641451
641448
641446
641445
641443
641441
641437
641436
641523
641555
641548
641547
641546
641545
641544
641542
641541
641536
641533
641532
641530...

result:

ok good plan

Test #26:

score: 0
Accepted
time: 17ms
memory: 19548kb

input:

1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

impossible

result:

ok impossible

Test #27:

score: 0
Accepted
time: 27ms
memory: 19448kb

input:

1
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))...

output:

impossible

result:

ok impossible

Test #28:

score: 0
Accepted
time: 30ms
memory: 19544kb

input:

1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

1

result:

ok good plan

Test #29:

score: 0
Accepted
time: 22ms
memory: 19580kb

input:

1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

impossible

result:

ok impossible

Test #30:

score: 0
Accepted
time: 16ms
memory: 19572kb

input:

1
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((...

output:

impossible

result:

ok impossible

Test #31:

score: 0
Accepted
time: 15ms
memory: 14600kb

input:

2
))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))...

output:

2
1

result:

ok good plan

Test #32:

score: 0
Accepted
time: 20ms
memory: 14604kb

input:

2
)()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

output:

impossible

result:

ok impossible

Test #33:

score: 0
Accepted
time: 23ms
memory: 19508kb

input:

3
)()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()(...

output:

3
1
2

result:

ok good plan

Test #34:

score: 0
Accepted
time: 102ms
memory: 42480kb

input:

1000000
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((((((
((((((...

output:

impossible

result:

ok impossible

Test #35:

score: 0
Accepted
time: 110ms
memory: 27656kb

input:

1000000
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))))))
))))))...

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 178ms
memory: 42568kb

input:

1000000
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))))))
((((((((((
))))))...

output:

666658
666688
666686
666684
666682
666680
666678
666676
666674
666672
666670
666668
666666
666664
666662
666660
666690
666656
666654
666652
666650
666648
666646
666644
666642
666640
666638
666636
666634
666632
666630
666720
666750
666748
666746
666744
666742
666740
666738
666736
666734
666732
666730...

result:

ok good plan

Test #37:

score: 0
Accepted
time: 170ms
memory: 46520kb

input:

999999
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)...

output:

833328
833343
833342
833341
833340
833339
833338
833337
833336
833335
833334
833333
833332
833331
833330
833329
833344
833327
833326
833325
833324
833323
833322
833321
833320
833319
833318
833317
833316
833315
833314
833359
833374
833373
833372
833371
833370
833369
833368
833367
833366
833365
833364...

result:

ok good plan

Test #38:

score: 0
Accepted
time: 196ms
memory: 43668kb

input:

1000000
)(
()(()))()((
)())
)()((((((
((((
))))))))()())((()(
)((
)())
))()((()
()
(
)(
()(
(((()((()())(()))(((())(((
)()()
)))(
(((
(()(()(())))(())))(((((
())())((()))(
(())
(()
()))(()(())()())(
())((
)))))))))
())()((())))(
()())((((()())()
((
()())
()((())
)()))))))))()())()))())
()())
)()())
...

output:

792159
360775
792142
360773
792148
792149
792150
792153
792154
575472
360779
360759
360756
360755
360754
360752
360751
575473
360746
360791
360812
360810
669464
360806
360805
360802
792137
360795
360793
575474
360789
669463
360787
792140
360785
792141
360783
360782
792196
360713
792181
792182
792184...

result:

ok good plan

Test #39:

score: 0
Accepted
time: 193ms
memory: 44144kb

input:

1000000
)()))))(()(((()
()((((()))
)())
)
()()(
()
())()((())))))())()(())(())
())))()())((
)()()((()((())
)
)()(
()()(
((())((
)(
(
)((()((()((()(())(()())
))()
())
()()()
(())
))()(()(()()()()((
(())))()((((()()(
(())
)())((()))
))(()
()()()(()(()()((((())))((())))(()()(()))))
(()()))()(())))()))(...

output:

564089
564128
564127
564119
564115
564114
564113
564111
564109
564106
564103
564102
564096
564135
564086
564082
564078
564077
564076
564071
564070
564069
564066
564061
564060
564163
564190
564187
564182
564181
564180
564179
564175
564174
564173
564172
564168
564059
564161
564160
564159
564156
564155...

result:

ok good plan

Test #40:

score: 0
Accepted
time: 22ms
memory: 3624kb

input:

564
)())((())((()))))(()())((((()()(()(()))(()((((()()))(((()))(()()()(()((()()()()((()))))((())))()(()((())(()())))))))())))(((())()()()))))()((((()()))()(()()())))(()()(())((())((()())(()()())()(((()))()())())))(((()(((((()())()())))()()((())))()()()(()()))()(()()()(((())())))(()(()(()((())()((()(...

output:

305
287
163
542
253
358
108
360
367
105
236
537
469
307
93
95
541
329
65
528
243
17
563
359
267
513
100
465
445
356
75
134
514
113
26
302
44
547
265
555
281
54
405
531
342
340
286
153
139
133
451
301
421
350
11
52
483
408
463
32
255
24
299
330
553
529
235
533
81
510
223
443
43
373
137
552
327
190
49...

result:

ok good plan

Test #41:

score: -100
Wrong Answer
time: 19ms
memory: 4108kb

input:

109
)(()((())()(())())))))((()(((()((()()())))()))()()()()))(()(()()((()()())())()))())(((()()))(()))))(()((()((()()(((()))()((((()(()()()(()))))))))())((())(())()((()))))((())()()())))))(())))())()())))())()(()))))(())()(((()((((()))))((()())()())())))())((()(()())()())((((()()(()((()))(())((()((()...

output:

impossible

result:

wrong answer you didn't find a solution but jury did