This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
template<class T> using V = vector<T>;
using vi = V<int>;
void solve() {
int N; cin >> N;
string S; cin >> S;
V<array<int, 2>> A(N); for(auto& x : A) { cin >> x[0] >> x[1]; --x[0], --x[1]; }
if (N % 2) {
cout << -1 << nl;
return;
}
vi I(2 * N);
for(int i = 0; i < N; i++) {
I[A[i][0]] = 2 * i;
I[A[i][1]] = 2 * i + 1;
}
vi ans(N), take(2 * N); int open = N / 2, closed = N / 2;
for(int i = 0; i < 2 * N; i++) if (I[i] != -1 && S[i] == '(' && open > 0) {
take[i] = 1; open--;
int x = I[i] / 2; ans[x] = I[i] % 2;
I[A[x][0]] = I[A[x][1]] = -1;
}
for(int i = 2 * N - 1; i >= 0; i--) if (I[i] != -1 && S[i] == ')' && closed > 0) {
take[i] = 1; closed--;
int x = I[i] / 2; ans[x] = I[i] % 2;
I[A[x][0]] = I[A[x][1]] = -1;
}
int bal = 0; for(int i = 0; i < 2 * N; i++) if (take[i]) {
if (S[i] == '(') bal++;
else bal--;
if (bal < 0) {
cout << -1 << nl;
return;
}
}
if (bal != 0) {
cout << -1 << nl;
return;
}
for(auto& x : ans) cout << x << " ";
cout << nl;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int T; cin >> T; while(T--) {
solve();
}
exit(0-0);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |