# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1264287 | duyanhloveav | Match (CEOI16_match) | C++20 | 12 ms | 12352 KiB |
#include <bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1LL)
using ll = long long;
const int mxn = 9 + 1e5;
const int inf = 0x3f3f3f3f;
const ll lnf = 0x3f3f3f3f3f3f3f3f;
int n, nxt[mxn][26];
char res[mxn];
string s;
void solve(int l, int r) {
if (l > r) return;
int p = nxt[r][s[l] - 'a'];
if (!p) {
cout << "-1\n";
exit(0);
}
res[l] = '(';
res[p] = ')';
solve(l + 1, p - 1);
solve(p + 1, r);
}
void _27augain(void) {
cin >> s;
n = s.size();
s = '*' + s;
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 26; ++j) {
if (s[i] - 'a' == j) {
nxt[i][j] = i;
} else {
nxt[i][j] = nxt[max(0, nxt[i - 1][s[i] - 'a'] - 1)][j];
}
}
}
solve(1, n);
for (int i = 1; i <= n; ++i) {
cout << res[i];
}
}
int32_t main(void) {
#define task "27augain"
cin.tie(0)->sync_with_stdio(0);
for (string iext : {"in", "inp"}) {
if (fopen((task "." + iext).c_str(), "r")) {
freopen((task "." + iext).c_str(), "r", stdin);
freopen(task ".out", "w", stdout);
}
}
int testcase = 1;
// cin >> testcase;
while (testcase--) {
_27augain();
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |