QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#217560 | #5108. Prehistoric Programs | drldrls | WA | 13ms | 3600kb | C++17 | 1.5kb | 2023-10-16 23:41:44 | 2023-10-16 23:41:44 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int main(){
// To get input n
int count{0};
cin >> count;
queue<vector<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 && (parentheses || s[0] != ')')){
parentheses += score;
result.emplace_back(i + 1);
}else{
vector<int> v{i + 1, score, s[0]};
q.emplace(v);
}
while(parentheses >= 0 && !q.empty()){
if(parentheses + q.front()[1] > 0){
parentheses += q.front()[1];
result.emplace_back(q.front()[0]);
q.pop();
}else{
break;
}
}
}
while(parentheses >= 0 && !q.empty() && (parentheses || q.front()[2] != ')')){
if(parentheses + q.front()[1] >= 0){
parentheses += q.front()[1];
result.emplace_back(q.front()[0]);
q.pop();
}else{
break;
}
}
if(parentheses == 0 && !result.empty() && q.empty()){
for(auto x: result) cout << x << " ";
}else{
cout << "impossible";
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 3600kb
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: 3480kb
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: 3452kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 1ms
memory: 3420kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 0ms
memory: 3468kb
input:
3 () ( )
output:
1 2 3
result:
ok good plan
Test #7:
score: 0
Accepted
time: 0ms
memory: 3456kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
5 ))( (() )( ( )
output:
2 3 4 1 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
3 (( ))()) (
output:
1 3 2
result:
ok good plan
Test #10:
score: 0
Accepted
time: 1ms
memory: 3364kb
input:
6 ) () ()()() (( ) )
output:
impossible
result:
ok impossible
Test #11:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
500 ( ) ) ( )( ( ( ) ))( ( ( ( ( ) ) ( ( ) ( ( ) ( ()(() ( )()) ( ( ) ( )()(( ( ) ( ) ) ( ( ( ) ( ( ) ) )( ( ( ) ) ( ) ( ( ( ) ( ( ()))) ( ( ( ) ( ) ) ( ( ) ) ( ( ( ( ( () ( ( ( ( ( (( ) ( ( ) ( ( ( ) ()) ( ( ( ) ( ( ( ) ) ( ) ) ( ) ( ( ( ( ) ( ) ) ) ) ( ) )))()( ( ) ) ( ) )( ) ( ) ) )) ( ( ( ( ( ( ...
output:
1 2 4 5 6 3 7 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 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 #12:
score: 0
Accepted
time: 0ms
memory: 3524kb
input:
50 ) ) ((((()())())))(())(()) ()(((())) (((()))(() ()((( )) ) )()))(()(()())(((((() ( ) ) )(( )()(( ())())) (())))() ((( ))))(() ()(())(()))())() ) ) ( ( ( ( ((())()())())))(((()) ()( (()(())()((() ()(((()())))())()( ) )((() ( ) (( ) ()( ( ( ) )))((()) ) ()))()(((()(() (( ((()))(())(()())(()())())()...
output:
3 4 5 1 2 6 7 8 9 10 11 12 13 14 15 16 17 18 22 23 24 19 25 20 26 27 28 21 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 46 45 47 48 49 50
result:
ok good plan
Test #13:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
50 ) ( )()( ())( ()()(((((())( )(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...
output:
2 3 4 5 1 6 7 8 9 10 11 12 13 14 15 16 18 19 20 21 17 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
result:
ok good plan
Test #14:
score: -100
Wrong Answer
time: 0ms
memory: 3528kb
input:
150 ))(()))(())(())))()))())()()()(())(((())))()))))() )))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...
output:
impossible
result:
wrong answer you didn't find a solution but jury did