QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69636#5108. Prehistoric Programsricky0129TL 120ms6516kbC++142.0kb2022-12-29 03:34:432022-12-29 03:34:46

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-29 03:34:46]
  • 评测
  • 测评结果:TL
  • 用时:120ms
  • 内存:6516kb
  • [2022-12-29 03:34:43]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define FOR(i,n) for(int i=0;i<n;i++)
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define f first
#define s second

const int MOD = (int)1e9+7;

struct obj{
    string val;
    int idx;
    int sum, left,right;
    obj(int sum=0,int left=0,int right=0) : sum(sum), left(left), right(right) {} 
    bool operator< (obj lhs) const {
        if(sum<=0 == lhs.sum<=0){
            if(sum<=0){
                return tie(left,sum)<tie(lhs.left,lhs.sum);
            }
            else return tie(right,sum)<tie(lhs.right,lhs.sum);
        }
        return tie(sum)<tie(lhs.sum);
    }
};
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<obj> A;
    FOR(i,n){
        string in;
        cin>>in;
        int curr = 0;
        int mini = INT_MAX;
        FOR(j,sz(in)){
            if(in[j]=='(') curr++;
            else curr--;
            mini = min(mini,curr);
        }
        int sum = curr;
        int maxi = INT_MAX;
        curr = 0;
        for(int j=sz(in)-1;j>=0;j--){
            if(in[j]==')') curr++;
            else curr--;
            maxi = min(maxi,curr);
        }
        obj x = obj(obj(-sum,-mini,maxi));
        x.idx = i+1;
        x.val = in;
        A.pb(x);
    }
    sort(A.begin(),A.end());
    //for(auto x: A) cout<<x.val<<endl;
    bool check = true;
    int open = 0;
    int close = 0;
    for(auto x: A){
        string in = x.val;
        FOR(i,sz(in)){
            if(in[i]==')') close++;
            else open++;
            if(close>open) check = false;
        }
    }
    if(open!=close) check = false;
    if(!check) cout<<"impossible\n";
    else{
        for(auto x: A){
            cout<<x.idx<<endl;
        }
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 120ms
memory: 6516kb

input:

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

output:

4238
2458
48374
389
6754
18533
6986
32583
23456
169
5803
31692
34539
10427
26677
35132
30771
39743
41740
24373
46194
25061
45491
5699
34110
23312
31402
33777
41641
28794
23551
41639
6701
7365
6381
35743
22710
42121
40415
3880
34723
20865
11768
35499
40332
30949
34479
15279
31817
35256
27864
17649
25...

result:

ok good plan

Test #2:

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

input:

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

output:

36
66
386
585
257
127
39
814
907
329
598
62
981
707
384
131
662
793
511
807
449
271
327
632
474
422
746
387
20
334
553
535
171
473
989
502
31
915
88
919
168
715
738
945
60
863
820
667
324
859
316
134
98
799
725
604
852
929
258
208
414
563
17
881
33
464
947
390
872
774
566
406
819
164
640
177
243
247...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
1
3

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

479
329
311
232
483
199
297
414
211
357
80
265
177
253
271
159
158
157
156
153
442
431
160
440
439
269
437
436
166
435
434
268
264
172
262
429
284
456
124
288
287
286
128
129
130
131
132
133
285
452
136
152
283
139
282
141
449
143
378
277
275
274
445
149
381
406
207
208
209
210
413
214
412
411
410
4...

result:

ok good plan

Test #12:

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

input:

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

output:

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

result:

ok good plan

Test #13:

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

input:

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

output:

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

result:

ok good plan

Test #14:

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

input:

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

output:

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

result:

ok good plan

Test #15:

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

input:

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

output:

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

result:

ok good plan

Test #16:

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

input:

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

output:

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

result:

ok good plan

Test #17:

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

input:

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

output:

468
390
396
4
122
1
601
657
274
79
180
158
526
485
730
547
25
571
131
530
41
166
43
103
246
164
55
56
230
341
494
418
395
481
408
606
406
243
622
605
495
250
624
469
281
625
238
587
618
160
609
255
612
258
225
259
265
162
263
264
650
176
492
181
182
184
185
186
172
654
191
169
653
661
651
195
470
64...

result:

ok good plan

Test #18:

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

input:

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

output:

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

result:

ok good plan

Test #19:

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

input:

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

output:

impossible

result:

ok impossible

Test #20:

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

input:

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

output:

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

result:

ok good plan

Test #21:

score: 0
Accepted
time: 4ms
memory: 3464kb

input:

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

output:

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

result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

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

input:

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

output:

impossible

result:

ok impossible

Test #24:

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

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: -100
Time Limit Exceeded

input:

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

output:

264227
770337
898404
83071
269214
857929
897909
731069
196234
352796
904916
134097
308325
501576
309146
592970
992894
748267
675083
900795
267140
619800
507757
610823
714320
902203
833824
769249
932913
799635
470977
175996
703503
799479
25080
164427
705720
356849
385146
999836
920721
466467
637563
6...

result: