#include<bits/stdc++.h>
using namespace std;
int n, l[100100], r[100100];
string z;
int ans[100100];
int gr[200200];
set<pair<int, int>> st, sto;
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);
for(register int i = 1; i <= n * 2; ++i){
if(z[i] != '.') tot += (z[i]=='('?1:-1);
auto it = st.begin();
while(it != st.end() && it->first <= i){
sto.insert({gr[it->first], it->second});
st.erase(it);
++it;
}
while(tot < 0 && !sto.empty()){
auto itr = sto.begin();
int pos = itr->first, j = itr->second;
pos = gr[pos];
z[pos] = '(', ++tot;
if(gr[pos] <= i){
++tot;
}
z[gr[pos]] = '.';
ans[j] ^= 1;
sto.erase(itr);
}
//if(tot < 0) return cout << -1 << '\n', void();
}
// cerr<<"gnrem"<<endl;
/*
while(tot < 0 && !sto.empty()){
auto itr = sto.begin();
int pos = itr->first, j = itr->second;
pos = gr[pos];
z[pos] = '(', ++tot;
++tot;
z[gr[pos]] = '.';
ans[j] ^= 1;
sto.erase(itr);
}
if(tot != 0) 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:50:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
50 | for(register int i = 1; i <= n * 2; ++i){
| ^
Main.cpp: In lambda function:
Main.cpp:120:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
120 | for(register int i = 0; i < (int)s.size(); ++i){
| ^
Main.cpp: In lambda function:
Main.cpp:130:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
130 | for(register int i = 1; i <= 2*n; ++i){
| ^
Main.cpp:136:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
136 | for(register int i = 1; i <= n; ++i) cout << ans[i] << ' ';
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
1228 KB |
Output is correct |
| 2 |
Correct |
14 ms |
1628 KB |
Output is correct |
| 3 |
Correct |
13 ms |
1956 KB |
Output is correct |
| 4 |
Correct |
15 ms |
2396 KB |
Output is correct |
| 5 |
Correct |
13 ms |
2388 KB |
Output is correct |
| 6 |
Correct |
9 ms |
2332 KB |
Output is correct |
| 7 |
Correct |
10 ms |
2648 KB |
Output is correct |
| 8 |
Correct |
15 ms |
3420 KB |
Output is correct |
| 9 |
Correct |
15 ms |
3400 KB |
Output is correct |
| 10 |
Correct |
16 ms |
3896 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
