QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116431#5108. Prehistoric Programsduongnc000WA 27ms5580kbC++202.4kb2023-06-28 22:51:462023-06-28 22:51:47

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-28 22:51:47]
  • 评测
  • 测评结果:WA
  • 用时:27ms
  • 内存:5580kb
  • [2023-06-28 22:51:46]
  • 提交

answer

/*
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt")
*/

#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<pii>
#define isz(x) (int)x.size()
using namespace std;

const int mxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;

int n;
pii p[mxN];
vi pos, neg;

bool cmp(int x, int y) {
	pii a = p[x], b = p[y];
	if(a.ff != b.ff) return (a.ff < b.ff);
	else return (a.ss > b.ss);
}

void kill() {
	cout << "impossible" << endl;
	exit(0);
}

void solve() {
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		string s; cin >> s;
		int sum = 0;
		for(char c : s)
			sum += (c == '(' ? 1 : -1);
		if(sum >= 0) {
			int cur_sum = 0, cur_min = 0;
			for(char c : s) {
				cur_sum += (c == '(' ? 1 : -1);
				cur_min = min(cur_min, cur_sum);
			}
			pos.emplace_back(i);
			p[i] = {-cur_min, cur_sum};
		}
		else {
			reverse(all(s));
			int cur_sum = 0, cur_min = 0;
			for(char c : s) {
				cur_sum += (c == ')' ? 1 : -1);
				cur_min = min(cur_min, cur_sum);
			}
			neg.emplace_back(i);
			p[i] = {-cur_min, cur_sum};
		}
	}
	sort(all(pos), cmp);
	sort(all(neg), cmp);
	int cur_sum_pos = 0;
	for(int &val : pos) {
		if(p[val].ff > cur_sum_pos)
			kill();
		cur_sum_pos += p[val].ss;
	}

	int cur_sum_neg = 0;
	for(int &val : neg) {
		if(p[val].ff > cur_sum_neg)
			kill();
		cur_sum_neg += p[val].ss;
	}

	if(cur_sum_pos != cur_sum_neg)
		kill();

	reverse(all(neg));
	pos.insert(pos.end(), all(neg));

	for(int &val : pos)
		cout << val << "\n";
}

signed main() {

#ifndef CDuongg
    if(fopen(taskname".inp", "r"))
        assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout));
#else
    freopen("bai3.inp", "r", stdin);
    freopen("bai3.out", "w", stdout);
    auto start = chrono::high_resolution_clock::now();
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t = 1; //cin >> t;
	while(t--) solve();

#ifdef CDuongg
	auto end = chrono::high_resolution_clock::now();
	cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '=';
	cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
#endif

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 11ms
memory: 4016kb

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

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: 1ms
memory: 3456kb

input:

2
()
()

output:

1
2

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
1
3

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
3
1
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

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

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
26
45
47
40
18
50
44
8
11
12
1
20
21
30
33
35
39
41
2
19
16
48
7
15
49

result:

ok good plan

Test #13:

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

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
23
12
7
9
14
20
22
24
25
27
1
32
34
35
38
43
45
48
49
50
30
39
17
36

result:

ok good plan

Test #14:

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

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
33
8
121
126
71
...

result:

ok good plan

Test #15:

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

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
40
111
97
96
79
139
116
81
20
78
108
137
130
125
133
73...

result:

ok good plan

Test #16:

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

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
72
144
41
22
20
28
95
16...

result:

ok good plan

Test #17:

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

input:

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

output:

468
163
390
379
204
396
707
590
585
4
122
1
405
657
658
601
79
180
34
274
104
473
158
149
681
571
547
504
526
730
269
705
485
108
25
230
341
103
426
395
156
406
218
246
382
494
41
43
481
408
418
131
55
56
606
166
164
530
357
378
358
581
361
362
578
574
368
369
371
374
624
326
636
622
287
618
294
612...

result:

ok good plan

Test #18:

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

input:

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

output:

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

result:

ok good plan

Test #19:

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

input:

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

output:

impossible

result:

ok impossible

Test #20:

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

input:

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

output:

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

result:

ok good plan

Test #21:

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

input:

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

output:

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

result:

ok good plan

Test #22:

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

input:

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

output:

impossible

result:

ok impossible

Test #23:

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

input:

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

output:

impossible

result:

ok impossible

Test #24:

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

input:

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

output:

impossible

result:

ok impossible

Test #25:

score: -100
Wrong Answer
time: 27ms
memory: 5580kb

input:

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

output:

impossible

result:

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