#include <bits/stdc++.h>
#define ll long long
#define vc vector
using namespace std;
int main() {
ll tcs;cin >> tcs;
while(tcs--){
ll n; cin >>n;
string s;cin >> s;
vc<vc<ll>> dod(2 * n);
vc<ll> p(2 * n), ans(n), a(n), b(n);
for(ll i = 0; i < n; ++i){
cin >> a[i] >> b[i];--a[i], --b[i];
if(s[a[i]]=='(' && s[b[i]]==')') ans[i]=1, dod[a[i]].push_back(i), --p[b[i]];
else if(s[a[i]]==')' && s[b[i]]=='(') ans[i]=0, dod[a[i]].push_back(i), --p[a[i]];
else if(s[a[i]]=='(' && s[b[i]]=='(') ans[i]=0, ++p[a[i]];
else if(s[a[i]]==')' && s[b[i]]==')') ans[i]=1, --p[b[i]];
else assert(0);
}
ll br=1, cur=0;
map<ll, ll> d;
for(ll i=0;br && i<2 * n;++i){
cur+=p[i];
for(auto v: dod[i]) d[b[v]]=v;
while(cur<0){
if(d.size()){
auto t=(*d.begin()).second; d.erase(d.begin());
if(a[t]<=i)++cur;
else assert(0);
if(b[t]<=i)++cur;
else ++p[b[t]];
ans[t]=!ans[t];
}
else{br=0;break;}
}
}
if(br && cur==0){
for(ll i=0;i<n;++i) cout << ans[i] <<" "; cout << endl;
vc<ll> vz(2 * n, 0);
//for(ll i=0;i<n;++i) vz[(ans[i])?b[i]:a[i]]=1;
//for(ll i=0;i<2 *n;++i) if(vz[i]) cout << s[i];cout <<endl;
}
else cout << - 1 << endl;
}
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:40:13: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
40 | for(ll i=0;i<n;++i) cout << ans[i] <<" "; cout << endl;
| ^~~
Main.cpp:40:55: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
40 | for(ll i=0;i<n;++i) cout << ans[i] <<" "; cout << endl;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
332 KB |
Output is correct |
2 |
Correct |
60 ms |
916 KB |
Output is correct |
3 |
Correct |
67 ms |
1132 KB |
Output is correct |
4 |
Correct |
69 ms |
1220 KB |
Output is correct |
5 |
Correct |
66 ms |
1168 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
320 KB |
Output is correct |
2 |
Correct |
50 ms |
2372 KB |
Output is correct |
3 |
Correct |
46 ms |
3096 KB |
Output is correct |
4 |
Correct |
52 ms |
4104 KB |
Output is correct |
5 |
Correct |
47 ms |
4976 KB |
Output is correct |
6 |
Correct |
34 ms |
5500 KB |
Output is correct |
7 |
Correct |
36 ms |
6472 KB |
Output is correct |
8 |
Correct |
45 ms |
7516 KB |
Output is correct |
9 |
Correct |
58 ms |
8612 KB |
Output is correct |
10 |
Correct |
58 ms |
9608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
54 ms |
1260 KB |
Output is correct |
3 |
Correct |
60 ms |
2956 KB |
Output is correct |
4 |
Correct |
55 ms |
4120 KB |
Output is correct |
5 |
Correct |
63 ms |
5572 KB |
Output is correct |
6 |
Correct |
62 ms |
6956 KB |
Output is correct |
7 |
Correct |
34 ms |
6148 KB |
Output is correct |
8 |
Correct |
46 ms |
9300 KB |
Output is correct |
9 |
Correct |
48 ms |
9580 KB |
Output is correct |
10 |
Correct |
62 ms |
12312 KB |
Output is correct |
11 |
Correct |
71 ms |
13868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
332 KB |
Output is correct |
2 |
Correct |
60 ms |
916 KB |
Output is correct |
3 |
Correct |
67 ms |
1132 KB |
Output is correct |
4 |
Correct |
69 ms |
1220 KB |
Output is correct |
5 |
Correct |
66 ms |
1168 KB |
Output is correct |
6 |
Correct |
44 ms |
320 KB |
Output is correct |
7 |
Correct |
50 ms |
2372 KB |
Output is correct |
8 |
Correct |
46 ms |
3096 KB |
Output is correct |
9 |
Correct |
52 ms |
4104 KB |
Output is correct |
10 |
Correct |
47 ms |
4976 KB |
Output is correct |
11 |
Correct |
34 ms |
5500 KB |
Output is correct |
12 |
Correct |
36 ms |
6472 KB |
Output is correct |
13 |
Correct |
45 ms |
7516 KB |
Output is correct |
14 |
Correct |
58 ms |
8612 KB |
Output is correct |
15 |
Correct |
58 ms |
9608 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
54 ms |
1260 KB |
Output is correct |
18 |
Correct |
60 ms |
2956 KB |
Output is correct |
19 |
Correct |
55 ms |
4120 KB |
Output is correct |
20 |
Correct |
63 ms |
5572 KB |
Output is correct |
21 |
Correct |
62 ms |
6956 KB |
Output is correct |
22 |
Correct |
34 ms |
6148 KB |
Output is correct |
23 |
Correct |
46 ms |
9300 KB |
Output is correct |
24 |
Correct |
48 ms |
9580 KB |
Output is correct |
25 |
Correct |
62 ms |
12312 KB |
Output is correct |
26 |
Correct |
71 ms |
13868 KB |
Output is correct |
27 |
Correct |
62 ms |
1340 KB |
Output is correct |
28 |
Correct |
71 ms |
3008 KB |
Output is correct |
29 |
Correct |
69 ms |
4308 KB |
Output is correct |
30 |
Correct |
81 ms |
5884 KB |
Output is correct |
31 |
Correct |
92 ms |
7096 KB |
Output is correct |
32 |
Correct |
51 ms |
8000 KB |
Output is correct |
33 |
Correct |
59 ms |
9676 KB |
Output is correct |
34 |
Correct |
66 ms |
11196 KB |
Output is correct |
35 |
Correct |
74 ms |
12800 KB |
Output is correct |
36 |
Correct |
92 ms |
14404 KB |
Output is correct |