#include<bits/stdc++.h>
using namespace std;
int n, l[1000100], r[1000100];
string z;
int ans[1000100];
set<pair<int, int>> pq;
set<int> st;
vector<int> tmp;
vector<pair<int, int>> v;
inline bool makni(int pos){
auto it = st.lower_bound(pos);
if(it == st.end()) return 0;
st.erase(it);
return 1;
}
signed main(){
ios_base::sync_with_stdio(0), cin.tie(0);
int T;
cin >> T;
function<void()> test_case = [](){
cin >> n >> z;
z = '.' + z;
st.clear(), pq.clear(), v.clear(), tmp.clear();
for(register int i = 1; i <= n; ++i){
cin >> l[i] >> r[i];
if(z[l[i]] == '(' && z[r[i]] == '('){
tmp.emplace_back(l[i]);
ans[i] = 0;
}else if(z[l[i]] == ')' && z[r[i]] == ')'){
st.insert(r[i]);
ans[i] = 1;
}else if(z[l[i]] == '(' && z[r[i]] == ')'){
st.insert(r[i]);
v.emplace_back(pair<int, int>{l[i], i});
ans[i] = 1;
}else{
st.insert(l[i]);
v.emplace_back(pair<int, int>{l[i], i});
ans[i] = 0;
}
}
// if(n & 1) return cout << -1 << '\n', void();
for(auto to : tmp){
if(!makni(to)) return cout << -1 << '\n', void();
}
sort(v.begin(), v.end());
int p = -1;
while(!st.empty()){
int lim = *st.begin();
while(p + 1 < (int)v.size() && v[p+1].first <= lim){
p++;
int ind = v[p].second;
pq.insert({r[ind], ind});
}
if(pq.empty()) return cout << -1 << '\n', void();
int ind = pq.begin()->second;
pq.erase(pq.begin());
ans[ind] ^= 1;
if(!makni(l[ind])) return cout << -1 << '\n', void();
if(!makni(r[ind])) return cout << -1 << '\n', void();
}
for(register int i = 1; i <= n; ++i){
cout << ans[i] << " \n"[i==n];
}
};
while(T--) test_case();
return 0;
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:42:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
42 | for(register int i = 1; i <= n; ++i){
| ^
Main.cpp:120:20: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
120 | for(register int i = 1; i <= n; ++i){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
4688 KB |
Output is correct |
2 |
Correct |
20 ms |
5212 KB |
Output is correct |
3 |
Correct |
24 ms |
5212 KB |
Output is correct |
4 |
Correct |
24 ms |
5212 KB |
Output is correct |
5 |
Correct |
24 ms |
5208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
4444 KB |
Output is correct |
2 |
Correct |
19 ms |
4912 KB |
Output is correct |
3 |
Correct |
18 ms |
4952 KB |
Output is correct |
4 |
Correct |
21 ms |
5468 KB |
Output is correct |
5 |
Correct |
19 ms |
5720 KB |
Output is correct |
6 |
Correct |
14 ms |
8024 KB |
Output is correct |
7 |
Correct |
16 ms |
8240 KB |
Output is correct |
8 |
Correct |
19 ms |
8536 KB |
Output is correct |
9 |
Correct |
21 ms |
8776 KB |
Output is correct |
10 |
Correct |
25 ms |
9016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
22 ms |
5536 KB |
Output is correct |
3 |
Correct |
23 ms |
6232 KB |
Output is correct |
4 |
Correct |
22 ms |
6492 KB |
Output is correct |
5 |
Correct |
30 ms |
7260 KB |
Output is correct |
6 |
Correct |
29 ms |
7580 KB |
Output is correct |
7 |
Correct |
20 ms |
9816 KB |
Output is correct |
8 |
Correct |
23 ms |
10072 KB |
Output is correct |
9 |
Correct |
19 ms |
10588 KB |
Output is correct |
10 |
Correct |
31 ms |
11332 KB |
Output is correct |
11 |
Correct |
34 ms |
12004 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
24 ms |
4688 KB |
Output is correct |
2 |
Correct |
20 ms |
5212 KB |
Output is correct |
3 |
Correct |
24 ms |
5212 KB |
Output is correct |
4 |
Correct |
24 ms |
5212 KB |
Output is correct |
5 |
Correct |
24 ms |
5208 KB |
Output is correct |
6 |
Correct |
16 ms |
4444 KB |
Output is correct |
7 |
Correct |
19 ms |
4912 KB |
Output is correct |
8 |
Correct |
18 ms |
4952 KB |
Output is correct |
9 |
Correct |
21 ms |
5468 KB |
Output is correct |
10 |
Correct |
19 ms |
5720 KB |
Output is correct |
11 |
Correct |
14 ms |
8024 KB |
Output is correct |
12 |
Correct |
16 ms |
8240 KB |
Output is correct |
13 |
Correct |
19 ms |
8536 KB |
Output is correct |
14 |
Correct |
21 ms |
8776 KB |
Output is correct |
15 |
Correct |
25 ms |
9016 KB |
Output is correct |
16 |
Correct |
1 ms |
4444 KB |
Output is correct |
17 |
Correct |
22 ms |
5536 KB |
Output is correct |
18 |
Correct |
23 ms |
6232 KB |
Output is correct |
19 |
Correct |
22 ms |
6492 KB |
Output is correct |
20 |
Correct |
30 ms |
7260 KB |
Output is correct |
21 |
Correct |
29 ms |
7580 KB |
Output is correct |
22 |
Correct |
20 ms |
9816 KB |
Output is correct |
23 |
Correct |
23 ms |
10072 KB |
Output is correct |
24 |
Correct |
19 ms |
10588 KB |
Output is correct |
25 |
Correct |
31 ms |
11332 KB |
Output is correct |
26 |
Correct |
34 ms |
12004 KB |
Output is correct |
27 |
Correct |
30 ms |
5460 KB |
Output is correct |
28 |
Correct |
39 ms |
6228 KB |
Output is correct |
29 |
Correct |
38 ms |
6740 KB |
Output is correct |
30 |
Correct |
44 ms |
7352 KB |
Output is correct |
31 |
Correct |
41 ms |
7596 KB |
Output is correct |
32 |
Correct |
28 ms |
9524 KB |
Output is correct |
33 |
Correct |
34 ms |
10204 KB |
Output is correct |
34 |
Correct |
40 ms |
11080 KB |
Output is correct |
35 |
Correct |
46 ms |
11320 KB |
Output is correct |
36 |
Correct |
51 ms |
11896 KB |
Output is correct |