#include <bits/stdc++.h>
using namespace std;
typedef pair<char, int> pci;
const int MAXN = 1e5;
int nextocc[MAXN];
int uf[MAXN+1];
int n;
bool seq[MAXN+1];
int rpair[MAXN+1];
class stree {
public:
int lp, rp;
stree *l = nullptr;
stree *r = nullptr;
bool has_extend = 0;
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 update(int v) { // set v to 1
if (lp > v || rp < v) return;
has_extend = 1;
if (lp < rp) {
l->update(v);
r->update(v);
}
}
bool query(int lv, int rv) {
if (lp > rv || rp < lv) return 0;
if (lp >= lv && rp <= rv) return has_extend;
return l->query(lv, rv)|r->query(lv, rv);
}
};
class stree2 {
public:
int lp, rp;
stree2 *l = nullptr;
stree2 *r = nullptr;
int mx_r;
stree2(int lv, int rv) {
lp = lv;
rp = rv;
mx_r = 0;
if (lp != rp) {
int m = (lp+rp)/2;
l = new stree2(lp, m);
r = new stree2(m+1, rp);
}
}
void update(int i, int v) {
if (lp > i || rp < i) return;
mx_r = max(mx_r, v);
if (lp < rp) {
l->update(i, v);
r->update(i, v);
}
}
int query(int lv, int rv) {
if (lp > rv || rp < lv) return 0;
if (lp >= lv && rp <= rv) return mx_r;
return max(l->query(lv, rv), r->query(lv, rv));
}
};
int find(int i) {
return (uf[i] == -1) ? i : (uf[i] = find(uf[i]));
}
stree *tree1;
stree2 *tree2;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
string s;
cin >> s;
n = s.size();
tree1 = new stree(0, n-1);
tree2 = new stree2(0, n-1);
map<char, int> occ;
for (int i = 0; i < n; i++) {
char c = s[i];
if (occ.find(c) != occ.end()) {
nextocc[occ[c]] = i;
}
occ[c] = i;
}
for (pci p: occ) nextocc[p.second] = n;
vector<pci> last;
for (int i = 0; i < n; i++) {
char c = s[i];
if (!last.empty() && c == last.back().first) {
seq[last.back().second] = 0;
seq[i] = 1;
tree2->update(last.back().second, i);
rpair[last.back().second] = i;
last.pop_back();
}
else last.push_back(pci(c, i));
}
if (!last.empty()) {
cout << "-1\n";
return 0;
}
fill(uf, uf+n+1, -1);
for (int i = 0; i < n; i++) {
if (seq[nextocc[i]]) uf[i] = nextocc[i];
}
for (int i = 0; i < n; i++) {
if (!seq[i]) {
tree1->update(rpair[i]);
continue;
}
int fpos = find(i);
int epos = nextocc[fpos];
if (epos == n) continue;
assert(!seq[epos]);
bool inv = tree1->query(fpos+1, epos-1);
inv |= (tree2->query(fpos+1, epos-1) > epos);
if (inv) continue;
uf[fpos] = epos;
tree1->update(epos);
seq[i] = 0;
seq[epos] = 1;
}
for (int i = 0; i < n; i++) {
if (seq[i]) cout << ")";
else cout << "(";
}
cout << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
