#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
#define f first
#define s second
#define LOGN 21
const ll MOD = 1e9 + 7;
const ll MAXN = 2e5 + 100;
#define int long long
int x[MAXN], y[MAXN];
vector<int> L[MAXN], R[MAXN];
void solve() {
int n;
string S;
cin >> n >> S;
S = "#" + S;
map<pair<int,int>,int> mp;
vector<int> ans(n+1, 0);
vector<int> active(2*n+1, 0);
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i];
if (S[x[i]] != S[y[i]]) {
mp[{x[i], y[i]}] = i;
mp[{y[i], x[i]}] = i;
R[y[i]].push_back(x[i]);
L[x[i]].push_back(y[i]);
}
if (S[x[i]] == '(' && S[y[i]] == '(') {
ans[i] = 0;
active[x[i]] = 1;
} else if (S[x[i]] == ')' && S[y[i]] == ')') {
ans[i] = 1;
active[y[i]] = 1;
} else if (S[x[i]] == '(' && S[y[i]] == ')') {
ans[i] = 1;
active[y[i]] = 1;
} else {
ans[i] = 0;
active[x[i]] = 1;
}
}
int cnt = 0;
set<pair<int,int>> completely_left;
set<pair<int,int>> partially_left;
for (int i = 1; i <= 2*n; i++) {
for (auto u : L[i])
partially_left.insert({u, i}); // {i, u}
for (auto u : R[i]) {
if (partially_left.count({i, u}) == 0)
continue;
completely_left.insert({u, i});
partially_left.erase({i, u}); // {u, i}
}
if (active[i]) {
if (S[i] == '(')
cnt++;
else
cnt--;
}
if (cnt < 0) {
if (completely_left.size()) {
int A = mp[*(completely_left.begin())];
swap(active[x[A]], active[y[A]]);
ans[A] ^= 1;
completely_left.erase(completely_left.begin());
cnt+=2;
} else if (partially_left.size()) {
int A = mp[*(partially_left.begin())];
swap(active[x[A]], active[y[A]]);
ans[A] ^= 1;
partially_left.erase(partially_left.begin());
cnt++;
} else {
cout << "-1\n";
exit(0);
}
}
}
if (cnt) {
cout << "-1\n";
return ;
}
for (int i = 1; i <= n; i++)
cout << ans[i] << " ";
cout << "\n";
for (int i = 1; i <= n; i++) {
R[y[i]].clear();
L[x[i]].clear();
}
}
signed main() {
fast;
int t;
cin >> t;
while (t--) {
solve();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
12888 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
12892 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
12888 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
12888 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |