This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
* author: wxhtzdy
* created: 17.08.2022 19:58:30
**/
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
string s;
cin >> s;
vector<int> a(n);
vector<int> b(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i];
--a[i]; --b[i];
}
string str = string(n, '?');
for (int i = 0; i < n; i++) {
if (s[a[i]] == s[b[i]]) {
str[i] = s[a[i]];
}
}
int cnt = 0;
for (int i = 0; i < n; i++) {
if (str[i] == '?') {
cnt += 1;
}
}
assert(cnt == 0);
vector<int> mn(n + 1);
for (int i = n - 1; i >= 0; i--) {
int x = 0;
if (str[i] == '(') {
x = +1;
}
if (str[i] == ')') {
x = -1;
}
mn[i] = min(x, x + mn[i + 1]);
}
int bal = 0;
for (int i = 0; i < n; i++) {
if (str[i] == '(') {
bal += 1;
continue;
}
if (str[i] == ')') {
bal -= 1;
continue;
}
if (bal > 0 && bal + mn[i + 1] > 0) {
str[i] = ')';
bal -= 1;
} else {
str[i] = '(';
bal += 1;
}
}
bal = 0;
bool ok = true;
for (int i = 0; i < n; i++) {
bal += (str[i] == '(' ? +1 : -1);
if (bal < 0) {
ok = false;
}
}
if (bal == 0 && ok) {
for (int i = 0; i < n; i++) {
cout << 0 << " ";
}
cout << '\n';
} else {
cout << -1 << '\n';
}
}
return 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... |