QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#66031 | #5108. Prehistoric Programs | bili2002# | WA | 17ms | 4280kb | C++17 | 3.9kb | 2022-12-06 00:48:14 | 2022-12-06 00:48:17 |
Judging History
answer
#include <bits/stdc++.h>
#define f first
#define s second
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
template<class T, class T2> inline bool chkmax(T &x, const T2 & y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 & y) { return x > y ? x = y, 1 : 0; }
template<class T, class T2> inline istream &operator>>(istream &is, pair<T, T2> &p) { is>>p.f>>p.s; return is; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const pair<T, T2> &p) { os<<p.f<<' '<<p.s; return os; }
template<class T> inline istream &operator>>(istream &is, vector<T> &v) { for (auto &id : v) is>>id; return is; }
template<class T> inline ostream &operator<<(ostream &os, const vector<T> &v) { for (auto id : v) os<<id<<'\n'; return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const map<T, T2> &m) { for (auto id : m) os<<id<<'\n'; return os; }
template<class T, class T2> inline ostream &operator<<(ostream &os, const unordered_map<T, T2> &um) { for (auto id : um) os<<id<<'\n'; return os; }
template<class T> inline ostream &operator<<(ostream &os, const list<T> &l) { for (auto id : l) os<<id<<' '; return os; }
template<class T> inline ostream &operator<<(ostream &os, const set<T> &s) { for (auto id : s) os<<id<<' '; return os; }
template<class T> inline ostream &operator<<(ostream &os, const unordered_set<T> &us) { for (auto id : us) os<<id<<' '; return os; }
const long long INF = 1e18;
const bool hasTests = 0;
struct par {
int op, cl;
int id;
bool neg;
int highestMin;
bool operator<(const par& oth) {
if (!neg && oth.neg) {
return true;
}
if (neg && !oth.neg) {
return false;
}
if (op - cl > 0 && oth.op - oth.cl < 0) {
return true;
}
if (op - cl < 0 && oth.op - oth.cl > 0) {
return false;
}
if (op - cl < 0) {
return highestMin < oth.highestMin;
} else {
return highestMin > oth.highestMin;
}
}
};
vector<par> p;
bool pos;
vector<int> ans;
int n;
void input() {
cin>>n;
p.resize(n);
string s;
for (int i=0; i<n; i++) {
cin>>s;
p[i].id = i;
p[i].neg = false;
for (auto curr : s) {
if (curr == '(') {
p[i].op++;
} else {
p[i].cl++;
}
if (p[i].op < p[i].cl) {
p[i].neg = true;
}
p[i].highestMin = min(p[i].highestMin, p[i].op - p[i].cl);
}
//cerr<<i<<' '<<p[i].highestMin<<' '<<p[i].neg<<endl;
}
}
void output() {
if (!pos) {
cout<<"impossible"<<endl;
return;
}
cout<<ans<<endl;
}
void solve() {
sort(all(p));
pos = true;
int cntOp = 0, cntCl = 0;
for (auto& curr : p) {
//cout<<curr.id<<' '<<cntOp + curr.highestMin<<' '<<cntCl<<endl;
if (cntOp + curr.highestMin < cntCl) {
pos = false;
break;
}
cntOp += curr.op;
cntCl += curr.cl;
ans.pb(curr.id + 1);
}
if (cntOp != cntCl) {
pos = false;
}
}
void start() {
int t = 1;
if (hasTests) {
cin>>t;
}
for (int i=1; i<=t; i++) {
input();
solve();
//cout<<"Case #"<<i<<": ";
output();
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
start();
return 0;
}
/*
7
((((()
()))))
(
)
((
))((
))
3
(((((
)))))((((
))))
2
()
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 17ms
memory: 4280kb
input:
50000 ( ( ))))()))()(()))()()()))()(((((()(((()))()(((()))((()(())))))(()( ) ( ) ((( ( ( ( ( ( () ( ) ( )((())()(( )))))( ( ) )) )() ( ) ) )()( ( ( () ( ) ( )()((((())()))())( ( ( )( ( ( (()())()) ) ) ( ( ( )((())))((())))))))))((((()()))()))))))))((()())())) ) )() ) ) ) ) ) ())(())))))()(()((()(())...
output:
26700 26740 26738 26737 26729 26727 26724 26723 26716 26715 26714 26713 26711 26709 26703 26744 26698 26696 26695 26693 26692 26689 26685 26682 26679 26677 26674 26672 26671 26670 26779 26819 26817 26815 26813 26810 26809 26806 26803 26802 26800 26792 26787 26784 26783 26668 26778 26777 26776 26773 ...
result:
ok good plan
Test #2:
score: 0
Accepted
time: 3ms
memory: 3312kb
input:
1000 ( ))(())) ((((())())))((())(()))( )( ) ))) ))((()(((((((())()(())()())))(()(())()())))))))((()((()())()())(())))()((()()) )((()()()(())(()))()(())()))(()))))())))))))))))))()))(()()(())(()))())()()))))(())()()()((())(()))(())))))))(()()())()))()())))()()))))))( )))((( ( )))()()()))) ( (((())(((...
output:
245 498 258 257 502 253 252 863 668 247 511 725 243 242 514 731 239 732 943 667 516 517 934 287 286 481 719 282 280 869 489 933 673 945 935 819 271 820 268 267 496 265 799 189 822 534 198 197 535 854 663 746 544 190 948 188 747 662 182 181 852 179 178 177 748 217 798 859 229 228 522 524 738 223 666 ...
result:
ok good plan
Test #3:
score: 0
Accepted
time: 1ms
memory: 3252kb
input:
2 () ()
output:
1 2
result:
ok good plan
Test #4:
score: 0
Accepted
time: 1ms
memory: 3252kb
input:
2 (( ))
output:
1 2
result:
ok good plan
Test #5:
score: 0
Accepted
time: 2ms
memory: 3376kb
input:
2 )( ()
output:
impossible
result:
ok impossible
Test #6:
score: 0
Accepted
time: 2ms
memory: 3368kb
input:
3 () ( )
output:
1 2 3
result:
ok good plan
Test #7:
score: 0
Accepted
time: 2ms
memory: 3152kb
input:
3 )( ( )
output:
2 1 3
result:
ok good plan
Test #8:
score: 0
Accepted
time: 0ms
memory: 3252kb
input:
5 ))( (() )( ( )
output:
2 4 3 1 5
result:
ok good plan
Test #9:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
3 (( ))()) (
output:
1 3 2
result:
ok good plan
Test #10:
score: 0
Accepted
time: 2ms
memory: 3404kb
input:
6 ) () ()()() (( ) )
output:
impossible
result:
ok impossible
Test #11:
score: 0
Accepted
time: 2ms
memory: 3392kb
input:
500 ( ) ) ( )( ( ( ) ))( ( ( ( ( ) ) ( ( ) ( ( ) ( ()(() ( )()) ( ( ) ( )()(( ( ) ( ) ) ( ( ( ) ( ( ) ) )( ( ( ) ) ( ) ( ( ( ) ( ( ()))) ( ( ( ) ( ) ) ( ( ) ) ( ( ( ( ( () ( ( ( ( ( (( ) ( ( ) ( ( ( ) ()) ( ( ( ) ( ( ( ) ) ( ) ) ( ) ( ( ( ( ) ( ) ) ) ) ( ) )))()( ( ) ) ( ) )( ) ( ) ) )) ( ( ( ( ( ( ...
output:
204 414 211 210 209 208 207 415 205 413 203 416 199 198 196 420 194 192 404 398 234 399 232 401 228 227 226 191 405 406 219 409 410 411 412 214 157 435 436 437 438 439 160 159 158 166 156 440 153 152 442 443 149 445 178 424 186 184 426 182 427 180 428 395 177 176 429 172 171 431 434 308 321 320 318 ...
result:
ok good plan
Test #12:
score: 0
Accepted
time: 2ms
memory: 3264kb
input:
50 ) ) ((((()())())))(())(()) ()(((())) (((()))(() ()((( )) ) )()))(()(()())(((((() ( ) ) )(( )()(( ())())) (())))() ((( ))))(() ()(())(()))())() ) ) ( ( ( ( ((())()())())))(((()) ()( (()(())()((() ()(((()())))())()( ) )((() ( ) (( ) ()( ( ( ) )))((()) ) ()))()(((()(() (( ((()))(())(()())(()())())()...
output:
17 32 34 28 27 36 25 24 23 22 37 38 43 3 4 5 10 6 13 31 29 14 46 42 9 45 44 50 49 18 40 26 15 7 48 47 19 16 2 33 8 11 12 41 39 20 21 1 35 30
result:
ok good plan
Test #13:
score: 0
Accepted
time: 1ms
memory: 3216kb
input:
50 ) ( )()( ())( ()()(((((())( )(())(()((())(()(()))(())())))))(())()))()())))))()(()()))(())))(()(((())(())()((())())()())(())())))()((()(()(())((()()))))()((((())()())((()))))((()()(())))))(()(())(()(()((())(()(())((()())))())(()))()())))()()((((()()((()()))((())())))()(())((()()((()((())())(()(()...
output:
2 47 46 41 40 33 28 26 18 16 15 13 11 5 8 37 29 21 6 31 36 12 17 23 39 43 38 4 42 32 44 45 3 1 48 49 50 35 34 30 7 27 25 24 22 20 19 9 10 14
result:
ok good plan
Test #14:
score: 0
Accepted
time: 3ms
memory: 3192kb
input:
150 ))(()))(())(())))()))())()()()(())(((())))()))))() )))()(()()(()((())())))(()(()(())((())))(((()(((())()()())))()())(((((((()))((())((())(())())(()))()(()()()()((((()))(()())))()(()((()(()(((((()((()())()))((((()))()))(()(((()()(((()(((()(((())(())())(()((()))))))()())((()(())())))((()()(()(((()...
output:
49 28 140 32 136 35 37 38 40 92 130 73 94 48 84 120 52 53 69 111 106 105 60 104 103 100 98 20 12 148 14 15 11 17 87 79 149 143 142 7 6 24 141 4 16 61 96 10 117 62 5 51 70 93 129 133 91 23 135 89 137 27 29 102 77 147 2 122 125 25 9 3 56 115 47 43 41 18 86 134 150 59 45 85 30 19 72 21 71 127 50 81 116...
result:
ok good plan
Test #15:
score: -100
Wrong Answer
time: 3ms
memory: 3248kb
input:
150 )))( (() (())((())))(()))()(() ((((()(((()))()(((((())()(()()((((()))((((()(())()(()))(()(())())(())(())))(((()))(())()))()((())((()(()(())())))))()(((()(()()())()))))()))(()(()()()(()(())()))))()))(((((())(()())((()()((((()))))(())())(())(())((()()(())))((((())((((()))()))()))))))))()()))))) ( ...
output:
impossible
result:
wrong answer you didn't find a solution but jury did