QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#70677#5108. Prehistoric ProgramsnvmdavaWA 13ms4156kbC++201.2kb2023-01-07 14:26:002023-01-07 14:27:33

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-07 14:27:33]
  • 评测
  • 测评结果:WA
  • 用时:13ms
  • 内存:4156kb
  • [2023-01-07 14:26:00]
  • 提交

answer

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

#define ll long long
#define ff first
#define ss second

vector<pair<pair<int, int>, int> > all;
string s;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;

    for(int i = 1; i <= n; ++i) {
        cin>>s;
        int mn = 0;
        int end = 0;
        for(char c : s) {
            if(c == '(') ++end;
            else --end;
            mn = min(mn, end);
        }
        all.push_back({{-mn, end}, i});
    }

    sort(all.begin(), all.end(), [](const pair<pair<int, int>, int>& lhs, const pair<pair<int, int>, int>& rhs) {
        if(lhs.ff.ss > 0) {
            if(rhs.ff.ss <= 0) return true;
            return lhs.ff.ff < rhs.ff.ff;
        } else {
            if(rhs.ff.ss > 0) return false;
            return lhs.ff.ff > rhs.ff.ff;
        }
    });

    int cur = 0;
    for(auto& x : all){
        if(cur < x.ff.ff) {
            cout<<"impossible\n";
            return 0;
        }
        cur += x.ff.ss;
    }
    if(cur != 0) {
        cout<<"impossible\n";
        return 0;
    }
    for(auto& x : all){
        cout<<x.ss<<'\n';
    }
}

详细

Test #1:

score: 100
Accepted
time: 13ms
memory: 4156kb

input:

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

output:

26315
26345
26341
26339
26336
26334
26333
26329
26328
26327
26321
26320
26318
26317
26316
26347
26313
26311
26308
26307
26305
26302
26297
26295
26294
26292
26290
26289
26286
26384
26414
26413
26412
26409
26406
26402
26401
26399
26398
26396
26395
26394
26393
26285
26383
26382
26380
26376
26370
26366
...

result:

ok good plan

Test #2:

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

input:

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

output:

252
267
573
265
799
859
258
257
929
575
253
268
640
576
933
247
707
245
243
242
934
239
287
915
803
301
863
919
296
481
291
290
570
798
286
801
282
925
280
554
553
271
819
945
820
619
198
943
584
793
854
190
189
188
719
585
725
182
181
947
179
178
177
948
638
715
935
577
496
498
711
857
229
228
502
...

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

input:

2
((
))

output:

1
2

result:

ok good plan

Test #5:

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

input:

2
)(
()

output:

impossible

result:

ok impossible

Test #6:

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

input:

3
()
(
)

output:

2
3
1

result:

ok good plan

Test #7:

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

input:

3
)(
(
)

output:

2
1
3

result:

ok good plan

Test #8:

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

input:

5
))(
(()
)(
(
)

output:

2
4
1
3
5

result:

ok good plan

Test #9:

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

input:

3
((
))())
(

output:

1
3
2

result:

ok good plan

Test #10:

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

input:

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

output:

impossible

result:

ok impossible

Test #11:

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

input:

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

output:

415
209
208
207
412
205
413
203
414
210
416
199
198
196
194
192
191
420
405
395
232
398
228
227
226
399
404
186
219
406
409
214
410
411
211
153
437
160
159
158
157
156
439
440
436
152
442
149
443
445
143
141
427
184
424
182
180
426
178
177
176
234
428
171
429
431
166
434
435
362
318
315
356
357
311
...

result:

ok good plan

Test #12:

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

input:

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

output:

impossible

result:

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