Submission #250366

#	Time	Username	Problem	Language	Result	Execution time	Memory
250366		dolphingarlic	Match (CEOI16_match)	C++14	100 / 100	17 ms	11648 KiB

match

#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];

void solve(int l = 0, int r = n - 1) {
    if (l > r) return;
    ans[l] = '(';
    ans[opt[r][s[l] - 'a']] = ')';
    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;
    solve();
    FOR(i, 0, n) cout << ans[i];
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63