#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<char, int> pci;
const int inf = 1e9;
class stree {
public:
int mn_contain = inf;
int lp, rp;
int lz = 0;
stree *l = nullptr;
stree *r = nullptr;
stree(int lv, int rv) {
lp = lv;
rp = rv;
if (lp != rp) {
int m = (lp+rp)/2;
l = new stree(lp, m);
r = new stree(m+1, rp);
}
}
void prop() {
if (l) {
l->lz += lz;
l->mn_contain += lz;
r->lz += lz;
r->mn_contain += lz;
}
lz = 0;
}
void update(int lv, int rv, int v) {
if (lp > rv || rp < lv) return;
prop();
if (lp >= lv && rp <= rv) {
mn_contain += v;
lz += v;
return;
}
l->update(lv, rv, v);
r->update(lv, rv, v);
mn_contain = min(l->mn_contain, r->mn_contain);
}
void update(int v, bool b = 1) {
if (lp > v || rp < v) return;
if (lp == rp) {
mn_contain = 0;
return;
}
l->update(v, b);
r->update(v, b);
mn_contain = min(l->mn_contain, r->mn_contain);
}
int mx_right(int lv, int rv) {
prop();
if (lp > rv || rp < lv || mn_contain) return 0;
if (lp == rp) {
return lp;
}
int rq = r->mx_right(lv, rv);
if (rq > 0) return rq;
return l->mx_right(lv, rv);
}
};
const int MAXN = 1e5;
int n;
stree *trees[26];
bool seq[MAXN];
int nums[MAXN];
int other[MAXN];
string s;
void make(int l, int r) {
if (r < l) return;
int pr = trees[nums[l]]->mx_right(l, r);
assert(pr > l);
assert(seq[pr]);
assert(nums[l] == nums[pr]);
assert(!seq[l]);
assert(seq[r]);
int va = other[l];
if (pr == va) {
for (int i = 0; i < 26; i++) trees[i]->update(l+1, pr-1, -1);
}
else {
int vb = other[pr];
other[va] = vb;
other[vb] = va;
other[l] = pr;
other[pr] = l;
seq[l] = seq[va] = 0;
seq[vb] = seq[pr] = 1;
for (int i = 0; i < 26; i++) {
trees[i]->update(l+1, va-1, -1);
trees[i]->update(vb+1, pr-1, -1);
trees[i]->update(va+1, vb-1, 1);
}
}
make(l+1, pr-1);
make(pr+1, r);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> s;
n = s.size();
for (int i = 0; i < 26; i++) trees[i] = new stree(0, n-1);
for (int i = 0; i < n; i++) {
nums[i] = s[i]-'a';
trees[nums[i]]->update(i);
}
vector<pii> open;
for (int i = 0; i < n; i++) {
if (!open.empty() && open.back().first == nums[i]) {
int prev = open.back().second;
other[prev] = i;
other[i] = prev;
seq[i] = 1;
open.pop_back();
}
else open.push_back(pii(nums[i], i));
}
if (!open.empty()) {
cout << "-1\n";
return 0;
} // mission failed... SUCCESSFULLY!
for (int i = n-1; i >= 0; i--) {
if (!seq[i]) {
for (int j = 0; j < 26; j++) trees[j]->update(i+1, other[i]-1, 1);
}
}
make(0, n-1);
char convert[2];
convert[0] = '(';
convert[1] = ')';
for (int i = 0; i < n; i++) {
cout << convert[seq[i]];
assert(other[other[i]] == i);
assert(seq[other[i]] != seq[i]);
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
2644 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
10 ms |
2644 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
