QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#379854 | #5108. Prehistoric Programs | cciafrino# | WA | 8ms | 3788kb | C++20 | 1.7kb | 2024-04-06 19:32:43 | 2024-04-06 19:32:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int N; cin >> N;
int total_balance = 0;
vector<int> good, bad;
vector<pair<int, int>> v(N);
for (int i =0; i < N; ++i) {
string S; cin >> S;
int minus = 0, plus = 0;
int balance = 0, min_balance = 1e9;
for (auto c : S) {
if (c == ')') {
minus++;
balance -= 1;
}
else {
plus++;
balance += 1;
}
min_balance = min(min_balance, balance);
}
v[i] = {min_balance, balance};
total_balance += balance;
if (balance < 0) {
bad.push_back(i);
} else {
good.push_back(i);
}
}
if (total_balance != 0) {
cout << "impossible\n";
} else {
sort(good.begin(), good.end(), [&](const auto& l, const auto& r) {
return v[l].first > v[r].first;
});
sort(bad.begin(), bad.end(), [&](const auto& l, const auto& r) {
return v[l].first - v[l].second < v[r].first - v[r].second;
});
int sum = 0;
bool works = true;
for (auto id : good) {
works |= (sum + v[id].first < 0);
sum += v[id].second;
}
for (auto id : bad) {
works |= (sum + v[id].first < 0);
sum += v[id].second;
}
if (works) {
for (int id : good) cout << id+1 << '\n';
for (int id : bad) cout << id+1 << '\n';
} else {
cout << "impossible\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 3788kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
30754 30788 30786 30781 30779 30778 30775 30771 30766 30765 30764 30790 30750 30748 30747 30746 30745 30743 30741 30737 30736 30735 30810 30860 30859 30857 30856 30855 30850 30847 30845 30834 30813 30734 30809 30804 30803 30799 30798 30797 30796 30793 30792 30791 30660 30680 30677 30672 30671 30669 ...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
655 685 287 681 680 291 673 668 667 666 663 301 662 309 659 316 282 324 652 327 329 650 646 334 335 640 636 632 628 347 615 611 252 216 217 752 748 223 228 229 747 746 738 242 243 732 245 247 604 253 257 258 725 719 715 711 265 267 268 707 271 689 687 280 516 422 557 426 554 553 430 544 535 534 439 ...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3524kb
input:
2 )( ()
output:
2 1
result:
wrong answer wrong plan (expected impossible)