QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#521476 | #5108. Prehistoric Programs | Andycipation | WA | 6ms | 3860kb | C++20 | 1.1kb | 2024-08-16 11:16:15 | 2024-08-16 11:16:15 |
Judging History
answer
/*
* author: ADMathNoob
* created: 08/15/24 23:11:42
* problem: https://qoj.ac/problem/5108
*/
/*
Comments about problem:
*/
#include <bits/stdc++.h>
using namespace std;
#ifdef _DEBUG
#include "debug.h"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<int> down(n), up(n);
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int mn = 0;
int sum = 0;
for (char c : s) {
int d = (c == '(' ? +1 : -1);
sum += d;
mn = min(mn, sum);
}
down[i] = mn;
up[i] = sum + mn;
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
return max(down[i], down[i] - up[i] + down[j]) < max(down[j], down[j] - up[j] + down[i]);
});
int at = 0;
for (int i : order) {
at -= down[i];
if (at < 0) {
cout << "impossible\n";
return 0;
}
at += up[i];
}
if (at != 0) {
cout << "impossible\n";
return 0;
}
for (int i : order) {
cout << i + 1 << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 3832kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
8378 8776 24534 12662 44055 21747 39764 28445 14821 27739 6827 34130 32506 15706 19829 21673 42674 32495 6916 14047 109 16769 15641 213 31585 38245 25565 36113 46482 11635 20550 6596 7478 633 3201 45612 39663 35457 30675 28930 16420 45933 46182 22204 29415 21519 41410 12925 20200 17735 1425 44459 37...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 1ms
memory: 3608kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
537 354 583 904 145 736 159 694 994 480 488 634 519 675 44 53 980 855 745 845 289 660 487 654 275 930 455 218 676 478 353 448 495 38 958 395 167 150 107 317 507 871 436 621 521 661 52 417 776 196 538 141 939 431 78 627 413 72 954 956 132 424 333 346 370 300 194 111 609 321 892 23 946 571 720 717 116...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3616kb
input:
2 )( ()
output:
1 2
result:
wrong answer wrong plan (expected impossible)