QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#521497#5108. Prehistoric ProgramsAndycipationWA 133ms27944kbC++201.4kb2024-08-16 11:30:022024-08-16 11:30:06

Judging History

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

  • [2024-08-16 11:30:06]
  • 评测
  • 测评结果:WA
  • 用时:133ms
  • 内存:27944kb
  • [2024-08-16 11:30:02]
  • 提交

answer

/*
 * author:  ADMathNoob
 * created: 08/15/24 23:11:42
 * problem: https://qoj.ac/problem/5108
 */

/*
Comments about problem:


*/

#include <bits/stdc++.h>

using namespace std;

#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  vector<int> down(n), up(n);
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    int mn = 0;
    int sum = 0;
    for (char c : s) {
      int d = (c == '(' ? +1 : -1);
      sum += d;
      mn = min(mn, sum);
    }
    down[i] = -mn;
    up[i] = sum + down[i];
  }
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    return min(-down[i], -down[i] + up[i] - down[j]) > min(-down[j], -down[j] + up[j] - down[i]);
    // return max(down[i], down[i] - up[i] + down[j]) < max(down[j], down[j] - up[j] + down[i]);
    bool goodI = (up[i] >= down[i]);
    bool goodJ = (up[j] >= down[j]);
    if (goodI != goodJ) return goodI;
    if (goodI) return down[i] < down[j];
    return up[i] > up[j];
  });
  int at = 0;
  for (int i : order) {
    at -= down[i];
    if (at < 0) {
      cout << "impossible\n";
      return 0;
    }
    at += up[i];
  }
  if (at != 0) {
    cout << "impossible\n";
    return 0;
  }
  for (int i : order) {
    cout << i + 1 << '\n';
  }
  return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 3936kb

input:

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

output:

26700
26740
26738
26737
26729
26727
26724
26723
26716
26715
26714
26713
26711
26709
26703
26744
26698
26696
26695
26693
26692
26689
26685
26682
26679
26677
26674
26672
26671
26670
26779
26819
26817
26815
26813
26810
26809
26806
26803
26802
26800
26792
26787
26784
26783
26668
26778
26777
26776
26773
...

result:

ok good plan

Test #2:

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

input:

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

output:

382
410
869
408
406
399
398
872
396
390
387
386
384
414
381
876
377
877
372
371
879
881
356
347
345
335
447
474
473
471
466
464
462
461
460
852
854
452
449
334
445
443
857
439
859
430
427
426
863
422
420
223
919
253
252
247
245
243
242
239
925
229
228
929
257
217
216
215
214
213
212
933
209
208
206
...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

1
2
3

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
1
3
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

203
211
210
209
208
207
413
205
414
412
415
416
199
198
196
194
420
192
404
234
232
398
399
228
227
226
401
191
405
406
219
409
410
214
411
156
436
437
438
439
160
159
158
157
435
440
153
152
442
443
149
445
143
178
424
186
184
426
182
427
180
428
395
177
176
429
172
431
434
166
360
318
315
353
311
...

result:

ok good plan

Test #12:

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

input:

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

output:

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

result:

ok good plan

Test #13:

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

input:

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

output:

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

result:

ok good plan

Test #14:

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

input:

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

output:

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

result:

ok good plan

Test #15:

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

input:

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

output:

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

result:

ok good plan

Test #16:

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

input:

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

output:

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

result:

ok good plan

Test #17:

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

input:

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

output:

648
624
625
632
304
635
636
294
287
645
281
622
274
269
651
265
264
263
653
259
258
654
345
368
362
361
605
606
358
357
609
612
348
255
343
341
338
335
618
333
331
330
326
324
680
213
212
671
672
208
673
204
674
677
195
214
191
681
186
185
184
182
181
180
684
176
231
657
250
658
246
661
243
663
238
...

result:

ok good plan

Test #18:

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

input:

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

output:

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

result:

ok good plan

Test #19:

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

input:

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

output:

impossible

result:

ok impossible

Test #20:

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

input:

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

output:

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

result:

ok good plan

Test #21:

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

input:

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

output:

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

result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

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

input:

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

output:

impossible

result:

ok impossible

Test #24:

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

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: 0
Accepted
time: 108ms
memory: 15164kb

input:

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

output:

541083
541063
541066
541070
541071
541072
541073
541075
541077
541082
541062
541084
541085
541087
541088
541093
541094
541097
541104
541108
541046
541031
541032
541035
541038
541039
541041
541042
541044
541045
541109
541051
541052
541053
541054
541055
541057
541058
541060
541162
541148
541150
541153...

result:

ok good plan

Test #26:

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

input:

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

output:

impossible

result:

ok impossible

Test #27:

score: 0
Accepted
time: 9ms
memory: 20076kb

input:

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

output:

impossible

result:

ok impossible

Test #28:

score: 0
Accepted
time: 10ms
memory: 20036kb

input:

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

output:

1

result:

ok good plan

Test #29:

score: 0
Accepted
time: 12ms
memory: 19860kb

input:

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

output:

impossible

result:

ok impossible

Test #30:

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

input:

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

output:

impossible

result:

ok impossible

Test #31:

score: 0
Accepted
time: 12ms
memory: 15168kb

input:

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

output:

2
1

result:

ok good plan

Test #32:

score: 0
Accepted
time: 8ms
memory: 15724kb

input:

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

output:

impossible

result:

ok impossible

Test #33:

score: 0
Accepted
time: 8ms
memory: 21164kb

input:

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

output:

3
1
2

result:

ok good plan

Test #34:

score: 0
Accepted
time: 50ms
memory: 14816kb

input:

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

output:

impossible

result:

ok impossible

Test #35:

score: 0
Accepted
time: 59ms
memory: 14804kb

input:

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

output:

impossible

result:

ok impossible

Test #36:

score: 0
Accepted
time: 94ms
memory: 14808kb

input:

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

output:

555562
555542
555544
555546
555548
555550
555552
555554
555556
555558
555560
555540
555564
555566
555568
555570
555572
555574
555576
555578
555580
555520
555502
555504
555506
555508
555510
555512
555514
555516
555518
555582
555522
555524
555526
555528
555530
555532
555534
555536
555538
555644
555624...

result:

ok good plan

Test #37:

score: 0
Accepted
time: 85ms
memory: 27944kb

input:

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

output:

666672
666657
666658
666659
666660
666661
666662
666663
666664
666665
666666
666667
666668
666669
666670
666671
666656
666673
666674
666675
666676
666677
666678
666679
666680
666681
666682
666683
666684
666685
666686
666641
666626
666627
666628
666629
666630
666631
666632
666633
666634
666635
666636...

result:

ok good plan

Test #38:

score: 0
Accepted
time: 133ms
memory: 14788kb

input:

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

output:

267506
576239
267524
576241
576243
576244
576253
576254
267514
576262
576264
576238
267505
576277
576278
267502
576281
267499
267498
267497
267495
576218
576194
576197
267550
576206
576211
576216
267543
576217
267541
576284
267539
576220
267537
576222
267533
576233
267529
576235
576236
267447
267463...

result:

ok good plan

Test #39:

score: 0
Accepted
time: 132ms
memory: 14724kb

input:

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

output:

621466
621454
238821
238820
621457
621459
238817
238816
621460
238814
621465
238823
238810
238809
621469
621470
621471
238805
621472
621475
621486
621445
621425
621428
238844
621429
621438
621439
621443
238837
621444
621487
621446
621447
621448
238831
238830
238829
621451
238825
621453
238756
621526...

result:

ok good plan

Test #40:

score: 0
Accepted
time: 11ms
memory: 4104kb

input:

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

output:

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

result:

ok good plan

Test #41:

score: 0
Accepted
time: 14ms
memory: 4416kb

input:

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

output:

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

result:

ok good plan

Test #42:

score: 0
Accepted
time: 21ms
memory: 3848kb

input:

64026
)()()()))((())((()(())())(()()())))(())))()))()(((())())))()))(()(()())((())((()(()))))()))())()(()(()))))())))(()()()()(((((()()()))))))((((()(()(())()))((()))))()())())(()(((()))))()))())))(()()()(())))((((())(())())(()()))()))))(())))()(((())()()()())()))))(())()(()(((())(()()()()((()()((()...

output:

23341
51708
46512
17624
12330
7398
30152
26531
51702
51701
9726
34028
7400
20527
18589
34026
34024
4377
30160
34023
59715
37637
43608
41253
36456
26521
18586
4425
54331
12300
9747
4421
12303
9742
7388
54336
39970
43628
19416
4367
12312
27684
37635
17629
12321
51715
20523
17627
34035
20525
30148
9711...

result:

ok good plan

Test #43:

score: 0
Accepted
time: 103ms
memory: 11908kb

input:

741507
)))((())))))()))(()()())((()((
))())
()
)(((()))()((()()(()())(())(((
(()))())()))))((
))(
)()
((()((()()()))(
(()(
(()())())(
)
)
(((()()(()(
()()(((
)(())))((((()((()()))))(()())(()))())((()((()((((()))()()(
()))
())())())))(()))(
())))()(
)(
(())()()())()())()((()))(
(())
)))()()
)
)(())()...

output:

246699
599898
599900
599903
599906
246709
246703
246702
246701
599897
246697
246695
246693
246692
246690
246689
246688
246687
246723
246725
599895
599893
246731
599890
599888
599886
246740
599880
246748
246751
599875
246760
246761
599961
246641
599942
599944
599946
599950
599953
246616
246615
599941...

result:

ok good plan

Test #44:

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

input:

32
())((())(()(((())())()())((())(()(((((((()))()(())))))())(())))((())((((()))(()(()(()(()))()(())())((()())(()((((((()(()(()()(()))()(())(()(()()))()())))()((()()(()(())))((()(()(()))))())()()(())(())(())()))(((()((((()())(()()()()()())()())())((()(()(()()
()
()))()()()(()())()((())))()((()()(()()...

output:

25
23
7
17
1
21
32
22
11
6
2
3
10
24
27
8
15
14
29
31
26
9
20
19
4
30
18
16
5
12
13
28

result:

ok good plan

Test #45:

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

input:

8
())(()()))))()(()))))()()(()()(())))((())))))(((())))))())((((()))((()))((())))()()))()(())(()(()()()(()())()(()((())()))(((((()(((()((()()((()()(())(()())()((()))))())()())(()))())(((((((()())(())))(()))))(())(())(()))))))(()(((()((()((((()))(()(((()))()))()())(((()))(((())(())))))(((())()()()))(...

output:

6
3
7
2
1
4
5
8

result:

ok good plan

Test #46:

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

input:

32
()))()(()))()()()()()(())((()()(()))(()
(()())())()))()(())())))()(()())()((()(()(()))()(()((((((((()))()))))((((())()))()((((()))((())()(()(()((()()()))))()()())()()((()(()()(((()))()))((()(()()(((()((())((((((((()())()(((()(()))(
)))()()()((())()()
())))((()))(()(((()((()()()))(()
)((()))))()))...

output:

23
29
27
14
31
8
4
28
2
21
17
13
32
6
20
26
7
19
18
10
15
22
24
1
3
11
9
12
25
16
5
30

result:

ok good plan

Test #47:

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

input:

53
))(((((())))))))((()()())()))())())())())(())())(())())(((()((()())(()(())))())(((
()()))((())))()))()(())))()))()(()(())))((())((((((()))()(()))))))))((()))))))))((())()))(()))())()()(()))()())()())())()(())(((()(
)())
()))))()))()(()()))()))(()((((()))(()))())(((()))(()()()))(())))(())))()(((((...

output:

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

result:

ok good plan

Test #48:

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

input:

25
)()((()())()))())))(((())))(())(()))))(()(()))((()()())(()((()())))(())())())())((()((()()(())))))))()((())())(()()(()()()())()())(()((()())(((())))()))(())()()()()((()))()(((())(())())((()((()))))(()(((()(())()()(((()))(()())(()))((())()))()))())(((()))))()()()((())((())()))()(())()(((((()())(((...

output:

25
21
5
11
19
14
9
12
20
7
13
22
1
15
4
16
8
6
24
17
23
10
2
18
3

result:

ok good plan

Test #49:

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

input:

90
))))((()()()))())))(
()())((((())))()))((())()()))))())(()()()(()))())))))((())())))()))(()())((())()(())))((((()(()()()())))()()))()(()())))())(((
))))())))()))))()((()(())(()((())(())()(()())))))()((()))((()()(()())()((()())((()()(()()(())())())()()(()))((()((()()(()()(()((()()()()))(())))))())...

output:

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

result:

ok good plan

Test #50:

score: -100
Wrong Answer
time: 0ms
memory: 3588kb

input:

16
))))))(((()(())()()(()((()()((())(()()(())))((())))))))(())(()))()((())((()(()()))())((())))()()()((()()))(((()()))()()))))()())))()))(((((()))(()()((()(()()()((((((()()(((((()(())))())()(())()())()(()(())()))()()()))(()(()))(())))(()))(((())))((((((()))(()((((())()())()(())()))()))(())()))))())(...

output:

impossible

result:

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