QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110365#5108. Prehistoric ProgramsjyhptrTL 29ms4476kbC++201.9kb2023-06-01 18:03:232023-06-01 18:03:25

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-01 18:03:25]
  • 评测
  • 测评结果:TL
  • 用时:29ms
  • 内存:4476kb
  • [2023-06-01 18:03:23]
  • 提交

answer

// compile: make data
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#else
#define debug(x...) {};
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define double long double
#define int long long
#define MAXN 200010

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    int n; cin >> n;
    struct node {
        int minv, sum, id;
    };
    vector<node> pos, neg;
    rep(i, 0, n) {
        string s; cin >> s;
        int minv = 0, sum = 0;
        rep(j, 0, s.length()) {
            if (s[j] == '(') sum++;
            else sum--;
            minv = min(minv, sum);
        }
        if (sum >= 0) pos.push_back({minv, sum, i+1});
        else neg.push_back({minv, sum, i+1});
    }
    sort(pos.begin(), pos.end(), [](node a, node b) {
        return a.minv > b.minv;
    });
    sort(neg.begin(), neg.end(), [](node a, node b) {
        return a.minv < b.minv;
    });
    int sum = 0;
    rep(i, 0, sz(pos)) {
        if (sum + pos[i].minv < 0) {
            print("impossible");
            return 0;
        }
        sum += pos[i].sum;
    }
    rep(i, 0, sz(neg)) {
        if (sum + neg[i].minv < 0) {
            print("impossible");
            return 0;
        }
        sum += neg[i].sum;
    }
    if (sum != 0) {
        print("impossible");
        return 0;
    }
    rep(i, 0, sz(pos)) cout << pos[i].id << endl;
    rep(i, 0, sz(neg)) cout << neg[i].id << endl;

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 29ms
memory: 4476kb

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: 4ms
memory: 3532kb

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: 2ms
memory: 3464kb

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible 

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

1
2
3

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible 

result:

ok impossible

Test #11:

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

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: 0ms
memory: 3444kb

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: 0ms
memory: 3392kb

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: 3472kb

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: 0ms
memory: 3404kb

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: 4ms
memory: 3416kb

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: 0ms
memory: 3404kb

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: 3ms
memory: 3452kb

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: 3384kb

input:

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

output:

impossible 

result:

ok impossible

Test #20:

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

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: 3ms
memory: 3380kb

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: 2ms
memory: 3516kb

input:

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

output:

impossible 

result:

ok impossible

Test #23:

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

input:

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

output:

impossible 

result:

ok impossible

Test #24:

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

input:

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

output:

impossible 

result:

ok impossible

Test #25:

score: -100
Time Limit Exceeded

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: