QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#390913#5108. Prehistoric ProgramsnocrizWA 9ms4204kbC++141.2kb2024-04-16 07:43:362024-04-16 07:43:36

Judging History

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

  • [2024-04-16 07:43:36]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:4204kb
  • [2024-04-16 07:43:36]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#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()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;


int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	int n;
	cin>>n;
	vector<pair<pii, int>> V0, V1;
	for(int i=0;i<n;i++) {
		string s;
		cin>>s;
		int su = 0, mi = 0;
		for(auto ct:s) {
			su += (ct == '(')?1 : -1;
			mi = min(mi, su);
		}
		if(su > 0) {
			V0.push_back(make_pair(make_pair(-mi, su), i+1));
		} else {
			V1.push_back(make_pair(make_pair(su-mi, -su), i+1));
		}
	}
	sort(V0.begin(), V0.end());
	sort(V1.begin(), V1.end());
	vector<int> ans0, ans1;
	int cs = 0;
	for(auto ct: V0) {
		if(cs-ct.first.first < 0) {
			cout<<"impossible\n";
			return 0;
		}
		cs += ct.first.second;
		ans0.push_back(ct.second);
	}
	cs = 0;
	for(auto ct: V1) {
		if(cs-ct.first.first < 0) {
			cout<<"impossible\n";
			return 0;
		}
		cs += ct.first.second;
		ans1.push_back(ct.second);
	}
	for(auto ct: ans0) {
		cout<<ct<<'\n';
	}
	reverse(all(ans1));

	for(auto ct: ans1) {
		cout<<ct<<'\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

1
2
5
8
9
10
11
12
14
16
19
23
27
28
30
32
34
35
37
38
42
43
44
55
58
59
61
70
72
79
80
87
91
92
93
94
95
96
97
99
112
116
118
120
122
125
126
127
128
131
135
136
146
147
148
149
150
151
165
166
175
177
179
181
182
183
185
186
187
191
192
193
194
195
196
199
205
207
209
210
211
218
220
225
229
230
2...

result:

ok good plan

Test #2:

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

input:

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

output:

1
3
10
12
14
18
22
54
58
64
65
75
77
89
90
92
97
101
104
106
110
122
125
126
135
136
143
147
162
166
178
179
181
182
188
189
190
198
206
209
212
213
215
216
217
223
228
229
242
243
245
247
252
253
265
267
268
280
282
287
290
291
301
309
313
335
347
356
371
372
377
381
382
396
398
399
408
410
420
426...

result:

ok good plan

Test #3:

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

input:

2
()
()

output:

2
1

result:

ok good plan

Test #4:

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
3
1

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
1
3
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

3
1
2

result:

ok good plan

Test #10:

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

input:

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

output:

4
6
5
1
3
2

result:

wrong answer wrong plan (expected impossible)