QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#582973 | #5108. Prehistoric Programs | deepthought | WA | 13ms | 7032kb | C++23 | 1.3kb | 2024-09-22 17:54:09 | 2024-09-22 17:54:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
pair<int, int> look(const string& s) {
int fin = 0;
int minima = 0;
for(int i = 0; i < s.length(); i++) {
if(s[i] == '(') fin++;
else fin--;
// if(s.length() == 150) cout << i << " " << fin << endl;
minima = min(fin, minima);
}
return {fin, minima};
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector <string> a(n + 1);
vector <pair <int, int>> v1;
vector <pair <int, int>> v2;
for(int i = 1; i <= n; i++) {
cin >> a[i];
auto ax = look(a[i]);
int minima = ax.second;
int fin = ax.first;
if(fin > 0) {
v1.push_back({-minima, i});
}
else {
v2.push_back({minima, i});
}
}
vector <int> ans;
string s = "";
sort(v1.begin(), v1.end());
for(auto x: v1) {
int idx = x.second;
s += a[idx];
ans.push_back(idx);
}
sort(v2.begin(), v2.end());
for(auto x: v2) {
int idx = x.second;
s += a[idx];
ans.push_back(idx);
}
auto bx = look(s);
if(bx.second >= 0 && bx.first == 0) {
for(auto x: ans)
cout << x << '\n';
}
else cout << "impossible" << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 13ms
memory: 7032kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
1 2 5 7 8 9 10 11 12 14 16 19 23 27 28 30 32 34 35 37 38 42 43 44 54 55 58 59 61 70 72 76 77 79 80 87 91 92 93 94 95 96 97 99 112 116 117 118 120 122 125 126 127 128 130 131 135 136 143 146 147 148 149 150 151 154 161 162 165 166 169 175 176 177 179 181 182 183 184 185 186 187 191 192 193 194 195 19...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 2ms
memory: 4096kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
1 3 10 12 13 14 17 18 20 22 31 33 36 39 54 58 60 62 64 65 66 75 77 80 83 88 89 90 92 97 98 101 104 106 110 122 125 126 127 131 134 135 136 143 147 162 164 166 168 171 177 178 179 181 182 188 189 190 198 206 208 209 212 213 214 215 216 217 223 228 229 239 242 243 245 247 252 253 257 258 265 267 268 2...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 0ms
memory: 3588kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
3 () ( )
output:
2 3 1
result:
ok good plan
Test #7:
score: 0
Accepted
time: 0ms
memory: 3844kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
5 ))( (() )( ( )
output:
2 4 1 3 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
3 (( ))()) (
output:
1 3 2
result:
ok good plan
Test #10:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
6 ) () ()()() (( ) )
output:
impossible
result:
ok impossible
Test #11:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
500 ( ) ) ( )( ( ( ) ))( ( ( ( ( ) ) ( ( ) ( ( ) ( ()(() ( )()) ( ( ) ( )()(( ( ) ( ) ) ( ( ( ) ( ( ) ) )( ( ( ) ) ( ) ( ( ( ) ( ( ()))) ( ( ( ) ( ) ) ( ( ) ) ( ( ( ( ( () ( ( ( ( ( (( ) ( ( ) ( ( ( ) ()) ( ( ( ) ( ( ( ) ) ( ) ) ( ) ( ( ( ( ) ( ) ) ) ) ( ) )))()( ( ) ) ( ) )( ) ( ) ) )) ( ( ( ( ( ( ...
output:
1 4 6 7 10 11 12 13 16 17 19 20 22 23 24 26 27 29 31 33 36 37 38 40 41 45 46 49 51 52 53 55 56 58 59 60 62 65 66 69 70 71 72 73 75 76 77 78 79 80 82 83 85 86 87 90 91 92 94 95 96 99 102 104 105 106 107 109 114 117 120 124 128 129 130 131 132 133 136 139 141 143 149 152 153 156 157 158 159 160 166 17...
result:
ok good plan
Test #12:
score: 0
Accepted
time: 0ms
memory: 3500kb
input:
50 ) ) ((((()())())))(())(()) ()(((())) (((()))(() ()((( )) ) )()))(()(()())(((((() ( ) ) )(( )()(( ())())) (())))() ((( ))))(() ()(())(()))())() ) ) ( ( ( ( ((())()())())))(((()) ()( (()(())()((() ()(((()())))())()( ) )((() ( ) (( ) ()( ( ( ) )))((()) ) ()))()(((()(() (( ((()))(())(()())(()())())()...
output:
4 5 6 10 17 22 23 24 25 27 28 32 34 36 37 38 43 13 14 31 46 42 9 45 44 50 18 49 15 26 40 7 16 19 47 48 1 2 8 11 12 20 21 29 30 33 35 39 41 3
result:
ok good plan
Test #13:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
50 ) ( )()( ())( ()()(((((())( )(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...
output:
2 5 8 11 13 16 18 26 28 40 41 46 47 37 29 21 6 31 12 36 17 23 39 1 3 4 7 9 10 14 19 20 22 24 25 27 30 32 34 35 38 42 43 44 45 48 49 50 15 33
result:
ok good plan
Test #14:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
150 ))(()))(())(())))()))())()()()(())(((())))()))))() )))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...
output:
4 6 7 11 12 14 15 17 24 28 32 35 37 38 40 49 52 60 69 73 79 84 87 92 94 98 100 104 105 106 111 120 140 141 142 143 148 149 10 16 23 27 51 61 62 70 89 91 93 133 135 29 77 102 147 2 3 9 25 122 125 18 43 47 56 86 134 150 59 30 45 19 72 21 71 127 50 81 116 63 31 8 121 66 126 33 55 54 132 1 42 95 109 57 ...
result:
ok good plan
Test #15:
score: 0
Accepted
time: 1ms
memory: 3656kb
input:
150 )))( (() (())((())))(()))()(() ((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()()))))) ( ...
output:
2 5 8 10 14 19 26 32 36 37 44 46 49 51 52 56 58 61 64 70 86 87 89 94 98 100 104 118 121 127 128 129 141 142 148 149 150 16 23 29 55 75 80 84 102 107 112 113 117 145 34 39 53 63 74 82 88 85 144 21 140 7 41 62 45 122 40 81 96 111 79 97 12 125 116 123 22 13 20 108 139 115 124 138 24 33 69 72 78 130 137...
result:
ok good plan
Test #16:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
150 )()(( ) )))()))) )()())((()(()())((())()))(()))(())((((((((()()(())())(()(((()))())()((()((())())))))))()((()))))((()(((()(((((()))()))((()((()()))(())))))()))))()())()()())(())(())(()))())((((((()()()))()((((()))))))((())()))()(()((()(())(())(())()())(()) ()() ) (())()))(())(()((())()()())())((...
output:
8 27 30 36 45 48 50 52 55 58 60 65 67 74 75 81 84 92 93 97 99 106 108 110 111 115 117 118 122 123 129 130 131 136 140 149 1 11 24 31 42 46 56 63 70 88 100 127 15 35 82 101 114 119 120 146 37 107 133 32 43 12 78 90 44 61 112 7 64 109 125 72 85 134 71 77 95 20 116 132 41 22 23 144 16 34 66 94 39 28 83...
result:
ok good plan
Test #17:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
750 (()()((()((((())()((()))()()))()))(()()(()))(()(())()))(((((( ))))))) ) ((()()()(())((()(()())(())(((()((((()))(()(())((())(()())(())())))())))()(())()))((()(()((((()(()))(()())()((()()()))))(())())(())())())()((()( ) ) ( )()(((()(())))()))))(((((((()))()()()(()())))(()())(()(( ( ) )(())) ((())(...
output:
1 4 7 9 13 16 17 20 21 22 25 27 34 37 41 43 45 48 55 56 57 62 65 66 67 69 74 79 81 82 95 97 101 103 104 108 112 116 121 122 131 136 138 141 148 149 150 152 155 156 157 158 159 160 162 163 164 166 169 172 175 176 180 181 182 184 185 186 191 195 204 208 212 213 214 218 220 224 225 227 228 229 230 231 ...
result:
ok good plan
Test #18:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
100 ) ) ) ( ) ( ))))() ) ( ( ( ( ) ) ) ) ( ( ( ( ()) ( ) ) )(( ) ( ( ( ) ( ( ) ) ) ) ()(( ( ) ) ) )((( (((( ( ) ( ) (( ) ( ( ) ( ())(())) ) ) ( ) ( ( ( ( )))()() ) ( ( ( ( ) ( ) ) ) ( ) ) ) ) ( ) ( ( ) ( ) ( ( ( ) ) ( ) ) ( )(((( ) ) ()((()()(())))) ) (
output:
4 6 9 10 11 12 17 18 19 20 22 27 28 29 31 32 37 38 43 44 46 48 50 51 53 57 59 60 61 62 65 66 67 68 70 74 79 81 82 84 86 87 88 91 94 100 25 42 95 7 63 54 1 2 3 5 8 13 14 15 16 21 23 24 26 30 33 34 35 36 39 40 41 45 47 49 52 55 56 58 64 69 71 72 73 75 76 77 78 80 83 85 89 90 92 93 96 97 98 99
result:
ok good plan
Test #19:
score: 0
Accepted
time: 0ms
memory: 3620kb
input:
100 ) ()( ( ) ( ) ( ( ) ) )(() ) ))) ) ) ( ( ( ) ( ( ) ( ) ( ( ( ))( ( ( ))(( ( ) ( ))()) ) (() ) ) ( ) ( ( ) ) ( ) ( )) ( ( ) ) ( ) ) ) ) ( ()) ) ( ( ) ) ( ) ( )) ( ) ) ( ( ((( ( ( (() ) )()())(()((()((()) ( ) ) ( ( ) ) ( ) ( ) ( ))( ) ( ( ( ) ( (((())
output:
impossible
result:
ok impossible
Test #20:
score: -100
Wrong Answer
time: 0ms
memory: 3556kb
input:
100 ) ) ()))(((( ))() ( ( ( ) ( ) ( ( ) () ( ( ) ) ( ) ( ( ) ) ) ( ) ) ( ( ) ) ( ) ) ) ) ( ( ) (( ( ( ) ) ( ( ) ( ) (()(( ) ( ) ) (()))()()())))()()(( ( ) ) ( ( ( ) ) ( ( ) ( ( ( ) ( ( ) )( ( ) ) ) ( (())())(() ) ) ( () (( ( ) ) ) ) ( ) ( ( ) ) ( ()) )(
output:
impossible
result:
wrong answer you didn't find a solution but jury did