QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#215570 | #5108. Prehistoric Programs | YYYYYYYY | WA | 15ms | 6292kb | C++14 | 3.2kb | 2023-10-15 11:52:43 | 2023-10-15 11:52:44 |
Judging History
answer
#include <iostream>
#include <cstring>
#include<string>
#include <vector>
int main() {
int n = 0;
std::string parentheses;
// int in[100000][2]={0};//[),(]
std::cin >> n;
int sum = 0;
std::vector<std::vector<int>> in(n, std::vector<int>(3, 0));
for (int i = 0; i < n; i++) {
std::cin >> parentheses;
int par = 0;
in[i][2]=i+1;
while(parentheses[par]!='\0'){
if(parentheses[par]=='('){
in[i][1] += 1;
}
else if(parentheses[par]==')'){
if(in[i][1]>0){
in[i][1] -= 1;
}
else {
in[i][0] += 1;
}
}
par++;
}
sum += in[i][0]-in[i][1];
// std::cout<<in[i][0]<<" "<<in[i][1];
}
if(sum!=0){
std::cout<<"impossible!!"<<sum;
return 0;
}
std::vector<int> v;
std::vector<int> value0;
std::vector<int> value1;
std::vector<int> right;
std::vector<int> left;
int middle = 0;
int cur[2]={0};
int flag = 0;
right.insert(right.begin(),0);
left.insert(left.begin(),0);
for(int i = 0; i < n; i++){
middle = v.size()/2;
if(in[i][1]==0 && in[i][0]!=0){//only)
// v.push_back(i+1);
// value0.push_back(in[i][0]);
// value1.push_back(in[i][1]);
// flag -= in[i][0];
right[0] += in[i][0];
right.push_back(i+1);
}
else if(in[i][0]==0 && in[i][1]!=0){
// v.insert(v.begin(), i+1);
// value0.insert(value0.begin(), in[i][0]);
// value1.insert(value1.begin(), in[i][1]);
// flag += in[i][1];
left[0] += in[i][1];
left.push_back(i+1);
}
else if(v.size()==0){
// std::cout<<"Y"<<middle;
v.insert(v.begin()+middle, i+1);
value0.insert(value0.begin()+middle, in[i][0]);
value1.insert(value1.begin()+middle, in[i][1]);
}
else if(in[i][0]-in[i][1]==0){
// std::cout<<"-->"<<flag;
// if(flag >0){
// middle++;
// }
v.insert(v.begin()+middle, i+1);
value0.insert(value0.begin()+middle, in[i][0]);
value1.insert(value1.begin()+middle, in[i][1]);
}
else if(in[i][0]-in[i][1]>0){//)多,放後
v.push_back(i+1);
value0.push_back(in[i][0]);
value1.push_back(in[i][1]);
}
else if(in[i][0]-in[i][1]<0){
v.insert(v.begin()+middle, i+1);
value0.insert(value0.begin()+middle, in[i][0]);
value1.insert(value1.begin()+middle, in[i][1]);
}
}
//v[i] = left+v+right
sum = left[0];
// std::cout<<"left"<<left[0]<<"right"<<right[0];
for(int i = 0; i < v.size(); i++){
// std::cout<<value0[i]<<"?";
sum -= value0[i];
if(sum<0){
std::cout<<"impossible";
return 0;
}
sum+=value1[i];
}
if(sum-right[0]<0){
// std::cout<<"impossible";
// return 0;
}
for (int i = 1; i < left.size(); i++) {
std::cout << left[i] << " ";
}
for (int i = 0; i < v.size(); i++) {
std::cout << v[i] << " ";
}
for (int i = 1; i < right.size(); i++) {
std::cout << right[i] << " ";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 15ms
memory: 6292kb
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: 3548kb
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: 3424kb
input:
2 () ()
output:
2 1
result:
ok good plan
Test #4:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 0ms
memory: 3408kb
input:
3 () ( )
output:
2 1 3
result:
ok good plan
Test #7:
score: 0
Accepted
time: 0ms
memory: 3412kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 0ms
memory: 3424kb
input:
5 ))( (() )( ( )
output:
2 4 3 1 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 0ms
memory: 3400kb
input:
3 (( ))()) (
output:
1 3 2
result:
ok good plan
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3496kb
input:
6 ) () ()()() (( ) )
output:
impossible!!1
result:
wrong answer wrong plan (expected impossible)