#include<bits/stdc++.h>
using namespace std;
int n, l[100002], r[100002];
string z;
int ans[100002];
int gr[200002];
set<pair<int, int>> st;
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0);
int T;
cin >> T;
function<void()> test_case = [](){
cin >> n >> z;
st.clear();
z = '.' + z;
for(register int i = 1; i <= n; ++i){
cin >> l[i] >> r[i];
gr[l[i]] = r[i];
gr[r[i]] = l[i];
if(z[l[i]] == '(' && z[r[i]] == '('){
ans[i] = 0;
z[r[i]] = '.';
}else if(z[l[i]] == ')' && z[r[i]] == ')'){
ans[i] = 1;
z[l[i]] = '.';
}else if(z[l[i]] == '(' && z[r[i]] == ')'){
st.insert({l[i], i});
z[l[i]] = '.';
ans[i] = 1;
}else{ // ) (
st.insert({r[i], i});
z[r[i]] = '.';
ans[i] = 0;
}
}
if(n & 1) return cout << -1 << '\n', void();
int tot(0);
bool flag = true;
for(register int i = 1; i <= 2*n && flag; ++i){
if(z[i] ^ '.') tot += (z[i]=='('?1:-1);
while(tot < 0 && !st.empty()){
int pos = st.begin()->first, j = st.begin()->second;
if(pos <= i){
z[pos] = '(', ++tot;
z[gr[pos]] = '.';
if(gr[pos] <= i) ++tot;
ans[j] ^= 1;
st.erase(st.begin());
}else{
// flag = false;
break;
}
}
}
if(!flag) return cout << -1 << '\n', void();
function<bool(const string)> is_valid = [](const string &s){
int tot(0);
for(register int i = 0; i < (int)s.size(); ++i){
tot += (s[i]=='('?1:-1);
if(tot < 0) return false;
}
return !tot;
};
string tmp = "";
for(register int i = 1; i <= 2*n; ++i){
if(z[i] == '.') continue;
tmp += z[i];
}
if(is_valid(tmp)){
for(register int i = 1; i <= n; ++i) cout << ans[i] << ' ';
}else{
cout << -1;
}
cout << '\n';
};
while(T--) test_case();
return 0;
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:23:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
23 | for(register int i = 1; i <= n; ++i){
| ^
Main.cpp:52:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
52 | for(register int i = 1; i <= 2*n && flag; ++i){
| ^
Main.cpp: In lambda function:
Main.cpp:85:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
85 | for(register int i = 0; i < (int)s.size(); ++i){
| ^
Main.cpp: In lambda function:
Main.cpp:95:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
95 | for(register int i = 1; i <= 2*n; ++i){
| ^
Main.cpp:101:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
101 | for(register int i = 1; i <= n; ++i) cout << ans[i] << ' ';
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
480 KB |
Output is correct |
| 2 |
Correct |
14 ms |
604 KB |
Output is correct |
| 3 |
Correct |
14 ms |
1020 KB |
Output is correct |
| 4 |
Correct |
15 ms |
1116 KB |
Output is correct |
| 5 |
Correct |
13 ms |
1464 KB |
Output is correct |
| 6 |
Correct |
12 ms |
1624 KB |
Output is correct |
| 7 |
Correct |
10 ms |
1880 KB |
Output is correct |
| 8 |
Correct |
14 ms |
2140 KB |
Output is correct |
| 9 |
Correct |
16 ms |
2272 KB |
Output is correct |
| 10 |
Correct |
22 ms |
2440 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
18 ms |
1372 KB |
Output is correct |
| 3 |
Correct |
28 ms |
2140 KB |
Output is correct |
| 4 |
Correct |
18 ms |
2392 KB |
Output is correct |
| 5 |
Correct |
21 ms |
2908 KB |
Output is correct |
| 6 |
Correct |
20 ms |
3660 KB |
Output is correct |
| 7 |
Correct |
16 ms |
3156 KB |
Output is correct |
| 8 |
Correct |
16 ms |
3928 KB |
Output is correct |
| 9 |
Correct |
17 ms |
4452 KB |
Output is correct |
| 10 |
Correct |
22 ms |
5180 KB |
Output is correct |
| 11 |
Correct |
25 ms |
5944 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
