oj.uz

Submission #250367

# Submission time Handle Problem Language Result Execution time Memory
250367 2020-07-17T15:09:31 Z dolphingarlic Match (CEOI16_match) C++14
100 / 100
 74 ms 17016 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

string s;
int n, opt[100000][26];
char ans[100000];

string solve(int l = 0, int r = n - 1) {
    if (l > r) return "";
    return '(' + solve(l + 1, opt[r][s[l] - 'a'] - 1) + ')' + solve(opt[r][s[l] - 'a'] + 1, r);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> s;
    n = s.size();
    stack<char> stck;
    FOR(i, 0, n) {
        if (stck.size() && s[i] == stck.top()) stck.pop();
        else stck.push(s[i]);
        FOR(j, 0, 26) {
            if (j == s[i] - 'a') opt[i][j] = i;
            else if (i && opt[i - 1][s[i] - 'a']) opt[i][j] = opt[opt[i - 1][s[i] - 'a'] - 1][j];
            else opt[i][j] = -1;
        }
    }
    if (stck.size()) return cout << -1, 0;
    cout << solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 2 ms 1024 KB Output is correct
9 Correct 3 ms 1408 KB Output is correct
10 Correct 2 ms 1408 KB Output is correct
11 Correct 2 ms 1664 KB Output is correct
12 Correct 22 ms 9720 KB Output is correct
13 Correct 29 ms 10616 KB Output is correct
14 Correct 46 ms 12664 KB Output is correct
15 Correct 72 ms 14840 KB Output is correct
16 Correct 72 ms 14840 KB Output is correct
17 Correct 56 ms 15480 KB Output is correct
18 Correct 52 ms 12288 KB Output is correct
19 Correct 54 ms 15128 KB Output is correct
20 Correct 48 ms 10880 KB Output is correct
21 Correct 74 ms 17016 KB Output is correct