# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
730738 | 2023-04-26T10:50:03 Z | Augustyn | Superpozicija (COCI22_superpozicija) | C++17 | 32 ms | 4424 KB |
#include<bits/stdc++.h> using namespace std; #define f first #define s second #define pf printf #define pii pair<int,int> pii ab[200001]; char naw[200001]; int jb[200001],gr[200001]; int t,n; void rozw() { scanf("%d",&n); priority_queue<pii ,vector<pii >,greater<pii >>dod; getchar(); for(int i=0;i<n*2;++i) naw[i]=getchar(); for(int i=0;i<n;++i) { scanf("%d%d",&ab[i].f,&ab[i].s); --ab[i].f; --ab[i].s; gr[ab[i].f]=ab[i].s; gr[ab[i].s]=ab[i].f; } int ile=0; for(int i=0;i<2*n;++i) { if(naw[gr[i]]==naw[i]) { if(naw[i]=='('&&i<gr[i]) { jb[i]=t; jb[gr[i]]=-t; ++ile; } else if(naw[i]==')'&&i>gr[i]) { jb[i]=t; jb[gr[i]]=-t; --ile; } } else { if(jb[i]!=-t&&jb[i]!=t) { if(naw[i]=='(') { jb[i]=-t; jb[gr[i]]=t; dod.push({gr[i],i}); } else { jb[i]=t; jb[gr[i]]=-t; --ile; dod.push({gr[i],i}); } } else if(jb[i]==t) { ile++; if(naw[i]==')') ile-=2; } } if(ile<0) { if(dod.empty()) { pf("-1\n"); return; } jb[dod.top().s]*=-1; jb[dod.top().f]*=-1; ++ile; if(max(dod.top().f,dod.top().s)<=i) ++ile; dod.pop(); } } if(ile!=0) { pf("-1\n"); return; } for(int i=0;i<n;++i) { if(jb[ab[i].f]==t) pf("0 "); else pf("1 "); } pf("\n"); } int main() { scanf("%d",&t); while(t) { rozw(); --t; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 1108 KB | Output is correct |
2 | Correct | 25 ms | 1068 KB | Output is correct |
3 | Correct | 23 ms | 1100 KB | Output is correct |
4 | Correct | 25 ms | 1184 KB | Output is correct |
5 | Correct | 25 ms | 1200 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 18 ms | 1108 KB | Output is correct |
2 | Correct | 18 ms | 1708 KB | Output is correct |
3 | Correct | 17 ms | 1868 KB | Output is correct |
4 | Correct | 20 ms | 2200 KB | Output is correct |
5 | Correct | 18 ms | 2356 KB | Output is correct |
6 | Correct | 11 ms | 2260 KB | Output is correct |
7 | Correct | 13 ms | 2636 KB | Output is correct |
8 | Correct | 15 ms | 3008 KB | Output is correct |
9 | Correct | 17 ms | 3388 KB | Output is correct |
10 | Correct | 22 ms | 4108 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 316 KB | Output is correct |
2 | Correct | 19 ms | 1368 KB | Output is correct |
3 | Correct | 19 ms | 1724 KB | Output is correct |
4 | Correct | 18 ms | 2004 KB | Output is correct |
5 | Correct | 23 ms | 2488 KB | Output is correct |
6 | Correct | 28 ms | 2732 KB | Output is correct |
7 | Correct | 10 ms | 1824 KB | Output is correct |
8 | Correct | 16 ms | 2924 KB | Output is correct |
9 | Correct | 19 ms | 3376 KB | Output is correct |
10 | Correct | 21 ms | 3808 KB | Output is correct |
11 | Correct | 23 ms | 4296 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 24 ms | 1108 KB | Output is correct |
2 | Correct | 25 ms | 1068 KB | Output is correct |
3 | Correct | 23 ms | 1100 KB | Output is correct |
4 | Correct | 25 ms | 1184 KB | Output is correct |
5 | Correct | 25 ms | 1200 KB | Output is correct |
6 | Correct | 18 ms | 1108 KB | Output is correct |
7 | Correct | 18 ms | 1708 KB | Output is correct |
8 | Correct | 17 ms | 1868 KB | Output is correct |
9 | Correct | 20 ms | 2200 KB | Output is correct |
10 | Correct | 18 ms | 2356 KB | Output is correct |
11 | Correct | 11 ms | 2260 KB | Output is correct |
12 | Correct | 13 ms | 2636 KB | Output is correct |
13 | Correct | 15 ms | 3008 KB | Output is correct |
14 | Correct | 17 ms | 3388 KB | Output is correct |
15 | Correct | 22 ms | 4108 KB | Output is correct |
16 | Correct | 1 ms | 316 KB | Output is correct |
17 | Correct | 19 ms | 1368 KB | Output is correct |
18 | Correct | 19 ms | 1724 KB | Output is correct |
19 | Correct | 18 ms | 2004 KB | Output is correct |
20 | Correct | 23 ms | 2488 KB | Output is correct |
21 | Correct | 28 ms | 2732 KB | Output is correct |
22 | Correct | 10 ms | 1824 KB | Output is correct |
23 | Correct | 16 ms | 2924 KB | Output is correct |
24 | Correct | 19 ms | 3376 KB | Output is correct |
25 | Correct | 21 ms | 3808 KB | Output is correct |
26 | Correct | 23 ms | 4296 KB | Output is correct |
27 | Correct | 27 ms | 1348 KB | Output is correct |
28 | Correct | 27 ms | 1876 KB | Output is correct |
29 | Correct | 25 ms | 2032 KB | Output is correct |
30 | Correct | 25 ms | 2588 KB | Output is correct |
31 | Correct | 27 ms | 2776 KB | Output is correct |
32 | Correct | 17 ms | 2596 KB | Output is correct |
33 | Correct | 18 ms | 3028 KB | Output is correct |
34 | Correct | 21 ms | 3524 KB | Output is correct |
35 | Correct | 25 ms | 3980 KB | Output is correct |
36 | Correct | 32 ms | 4424 KB | Output is correct |