QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#390913 | #5108. Prehistoric Programs | nocriz | WA | 9ms | 4204kb | C++14 | 1.2kb | 2024-04-16 07:43:36 | 2024-04-16 07:43:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n;
cin>>n;
vector<pair<pii, int>> V0, V1;
for(int i=0;i<n;i++) {
string s;
cin>>s;
int su = 0, mi = 0;
for(auto ct:s) {
su += (ct == '(')?1 : -1;
mi = min(mi, su);
}
if(su > 0) {
V0.push_back(make_pair(make_pair(-mi, su), i+1));
} else {
V1.push_back(make_pair(make_pair(su-mi, -su), i+1));
}
}
sort(V0.begin(), V0.end());
sort(V1.begin(), V1.end());
vector<int> ans0, ans1;
int cs = 0;
for(auto ct: V0) {
if(cs-ct.first.first < 0) {
cout<<"impossible\n";
return 0;
}
cs += ct.first.second;
ans0.push_back(ct.second);
}
cs = 0;
for(auto ct: V1) {
if(cs-ct.first.first < 0) {
cout<<"impossible\n";
return 0;
}
cs += ct.first.second;
ans1.push_back(ct.second);
}
for(auto ct: ans0) {
cout<<ct<<'\n';
}
reverse(all(ans1));
for(auto ct: ans1) {
cout<<ct<<'\n';
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 9ms
memory: 4204kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
1 2 5 8 9 10 11 12 14 16 19 23 27 28 30 32 34 35 37 38 42 43 44 55 58 59 61 70 72 79 80 87 91 92 93 94 95 96 97 99 112 116 118 120 122 125 126 127 128 131 135 136 146 147 148 149 150 151 165 166 175 177 179 181 182 183 185 186 187 191 192 193 194 195 196 199 205 207 209 210 211 218 220 225 229 230 2...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
1 3 10 12 14 18 22 54 58 64 65 75 77 89 90 92 97 101 104 106 110 122 125 126 135 136 143 147 162 166 178 179 181 182 188 189 190 198 206 209 212 213 215 216 217 223 228 229 242 243 245 247 252 253 265 267 268 280 282 287 290 291 301 309 313 335 347 356 371 372 377 381 382 396 398 399 408 410 420 426...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 0ms
memory: 3560kb
input:
2 () ()
output:
2 1
result:
ok good plan
Test #4:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 1ms
memory: 3792kb
input:
3 () ( )
output:
2 3 1
result:
ok good plan
Test #7:
score: 0
Accepted
time: 1ms
memory: 3612kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
5 ))( (() )( ( )
output:
2 4 1 3 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
3 (( ))()) (
output:
3 1 2
result:
ok good plan
Test #10:
score: -100
Wrong Answer
time: 0ms
memory: 3868kb
input:
6 ) () ()()() (( ) )
output:
4 6 5 1 3 2
result:
wrong answer wrong plan (expected impossible)