Submission #567366

#	Time	Username	Problem	Language	Result	Execution time	Memory
567366		piOOE	Match (CEOI16_match)	C++17	100 / 100	20 ms	13012 KiB

match

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) ((int)size(x))
#define trace(x) cout << #x << ": " << (x) << endl;

typedef long long ll;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const int A = 26, N = 100000;

int mx_prv[N][A];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s, ans;
    cin >> s;
    int n = sz(s);
    ans.resize(n);
    memset(mx_prv, -1, sizeof(mx_prv));
    for (int i = 1; i < n; ++i) {
        mx_prv[i][s[i] - 'a'] = i;
        for (int c = 0; c < A; ++c) {
            int j = mx_prv[i - 1][s[i] - 'a'] - 1;
            if (j >= 0 && mx_prv[i][c] == -1) {
                if ((s[j] - 'a') == c) {
                    mx_prv[i][c] = j;
                } else {
                    mx_prv[i][c] = mx_prv[j][c];
                }
            }
        }
    }
    vector<int> st;
    for (int i = 0; i < n; ++i) {
        if (st.empty() || s[st.back()] != s[i]) {
            st.push_back(i);
        } else {
            st.pop_back();
        }
    }
    if (!st.empty()) {
        cout << -1;
        return 0;
    }
    function<void(int, int)> solve = [&](int l, int r) {
        if (l >= r) return;
        int m = mx_prv[r][s[l] - 'a'];
        ans[l] = '(', ans[m] = ')';
        solve(l + 1, m - 1), solve(m + 1, r);
    };
    solve(0, n - 1);
    cout << ans;
    return 0;
}

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