QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#217538 | #5108. Prehistoric Programs | drldrls | WA | 13ms | 3540kb | C++17 | 1.5kb | 2023-10-16 23:03:09 | 2023-10-16 23:03:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main(){
// To get input n
int count{0};
cin >> count;
queue<pair<int, int>> q; // a queue to save strings that haven't been used
vector<int> result(0); // save permutation results
int parentheses{0}; // save the current score: numbers of '(' - numbers of ')'
// iterate *count* times to receive inputs
for(int i = 0; i < count; i++){
string s;
int score{0};
cin >> s;
score = 2 * std::count(s.begin(), s.end(), '(') - s.length();
if(parentheses + score >= 0 && (!result.empty() || s[0] != ')')){
parentheses += score;
result.emplace_back(i + 1);
}else{
q.emplace(make_pair(i + 1, score));
}
while(parentheses >= 0 && !q.empty()){
if(parentheses + q.front().second > 0){
parentheses += q.front().second;
result.emplace_back(q.front().first);
q.pop();
}else{
break;
}
}
}
while(parentheses >= 0 && !q.empty()){
if(parentheses + q.front().second >= 0){
parentheses += q.front().second;
result.emplace_back(q.front().first);
q.pop();
}else{
break;
}
}
if(parentheses == 0 && !result.empty()){
for(auto x: result) cout << x << " ";
}else{
cout << "impossible";
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 13ms
memory: 3540kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
1 2 3 5 6 7 4 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 46 47 48 49 50 51 52 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 45 53 74 75 101 102 ...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 2ms
memory: 3428kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
1 3 4 5 9 10 12 13 2 6 7 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 8 11 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...
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: 0ms
memory: 3460kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: -100
Wrong Answer
time: 0ms
memory: 3468kb
input:
2 )( ()
output:
2 1
result:
wrong answer wrong plan (expected impossible)