QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#63932#5108. Prehistoric ProgramsNoobie_99WA 9ms6104kbC++201.6kb2022-11-23 18:32:132022-11-23 18:32:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-23 18:32:16]
  • 评测
  • 测评结果：WA
  • 用时：9ms
  • 内存：6104kb
查看
  • [2022-11-23 18:32:13]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define debug(x) cerr << "[" << __LINE__ << ' ' << #x << "]: " << (x) << endl

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n;
    cin >> n;

    vector<tuple<int, int, string, int>> a, b;
    for (int i=0; i<n; i++) {
        string s;
        cin >> s;
        int cur = 0, mn = 0, mx = 0;
        for (char c : s) {
            if (c == '(') cur++;
            else cur--;
            mn = min(mn, cur);
            mx = max(mx, cur);
        }
        if (cur >= 0) a.emplace_back(mn, cur, s, i);
        else b.emplace_back(-mx, -cur, s, i);
    }

    sort(a.begin(), a.end(), [&](auto& x, auto& y) {
        if (get<0>(x) != get<0>(y)) return get<0>(x) > get<0>(y);
        return get<1>(x) > get<1>(y);
    });
    sort(b.begin(), b.end(), [&](auto& x, auto& y) {
        if (get<0>(x) != get<0>(y)) return get<0>(x) < get<0>(y);
        return get<1>(x) > get<1>(y);
    });

    vector<int> ans;
    int cur = 0;
    bool flag = true;
    for (auto& [x, _, y, z] : a) {
        for (char c : y) {
            if (c == '(') cur++;
            else cur--;
            if (cur < 0) flag = false;
        }
        ans.push_back(z);
    }
    for (auto& [x, _, y, z] : b) {
        for (char c : y) {
            if (c == '(') cur++;
            else cur--;
            if (cur < 0) flag = false;
        }
        ans.push_back(z);
    }

    if (cur != 0 || !flag) cout << "impossible\n";
    else {
        for (int e : ans) cout << e+1 << '\n';
    }

}
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 9ms
memory: 6104kb

input:

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

output:

41248
4238
13809
5338
27609
2458
389
48374
48749
6754
18533
42979
14096
6986
5803
32583
23456
31692
3405
169
26677
9225
26695
10427
38930
43508
34539
35132
30771
21764
25061
2253
24373
39743
46194
11398
46429
41740
31402
34110
35039
33777
45491
5699
23312
28794
41641
41639
6381
463
9790
35743
6701
3...

result:

ok good plan

Test #2:

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

input:

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

output:

36
13
66
386
966
585
286
257
127
83
39
476
595
329
598
214
814
907
427
62
981
707
384
662
131
807
793
511
80
271
869
449
767
638
379
746
474
239
327
422
632
20
387
715
535
31
975
88
989
473
296
168
171
334
553
345
502
919
915
464
164
563
134
738
566
731
725
575
481
604
686
208
258
177
667
640
827
60...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
1
3

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

311
329
479
232
443
483
199
80
414
297
177
265
253
357
350
211
325
290
362
296
308
309
351
315
318
320
321
340
327
349
345
330
353
334
338
344
343
339
262
234
239
1
241
242
243
247
248
249
251
254
256
258
288
264
268
269
271
274
275
277
282
283
284
285
286
287
459
428
429
431
434
435
436
437
439
440...

result:

ok good plan

Test #12:

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

input:

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

output:

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

result:

ok good plan

Test #13:

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

input:

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

output:

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

result:

ok good plan

Test #14:

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

input:

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

output:

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

result:

ok good plan

Test #15:

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

input:

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

output:

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

result:

ok good plan

Test #16:

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

input:

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

output:

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

result:

ok good plan

Test #17:

score: -100
Wrong Answer
time: 3ms
memory: 3492kb

input:

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

output:

impossible

result:

wrong answer you didn't find a solution but jury did
English 繁體中文 简体中文

Server Time: 2024-12-05 12:14:31 | OpenSource Project