Submission #1117665

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117665		Captain_Georgia	Match (CEOI16_match)	C++17	10 / 100	93 ms	7504 KiB

match

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int32_t main () {

    ios_base::sync_with_stdio(0); 
    cin.tie(0); 
    cout.tie(0); 

    int N;
    string S;
    cin >> S;
    S = '-' + S;
    N = S.size();
    if (N % 2 == 0) {
        cout << "-1\n";
        return 0;
    }
    vector<vector<set<int>>> ind(26, vector<set<int>>(2));
    for (int i = 1;i < N;i ++) {
        ind[S[i] - 'a'][i % 2].insert(i);
    }
    vector<vector<int>> dp(N + 1, vector<int> (N + 1, 0));
    vector<vector<int>> go(N + 1, vector<int> (N + 1, 0));
    for (int i = 1;i <= N;i ++) {
        for (int j = 1;j < i;j ++) {
            dp[i][j] = 1;
        }
    }
    for (int len = 2;len < N;len += 2) {
        for (int l = 1, r = len;r < N;r ++, l ++) {
            if (S[l] == S[r] && dp[l + 1][r - 1] == 1) {
                dp[l][r] = 1;
                go[l][r] = -1;
            } else {
                auto _r = ind[S[l] - 'a'][1 - l % 2].lower_bound(r);
                while (_r != ind[S[l] - 'a'][1 - l % 2].begin()) {
                    // cerr << "while _r != ind[S[l] - 'a'][l % 2].begin()\n";
                    _r = prev(_r);
                    // if (l == 2 && r == 5) {
                    //     cout << *_r << " " << dp[l + 1][*_r - 1] << " " << dp[*_r + 1][r] << "\n";
                    // }
                    if (dp[l][*_r] == 1 && S[*_r + 1] == S[r] && dp[*_r + 1][r] == 1) {
                        dp[l][r] = 1;
                        go[l][r] = *_r;
                        break;
                    }
                }
            }
        }
    }
    // for (int i = 1;i < N;i ++) {
    //     for (int j = i;j < N;j ++) {
    //         cout << dp[i][j] << " ";
    //     } cout << "\n";
    // }
    if (dp[1][N - 1] == 0) {
        cout << "-1\n";
        return 0;
    }
    string ans(N, ' ');
    function<void(int, int)> get_answer = [&](int l, int r) -> void {
        if (l > r || l <= 0 || l > N - 1 || r <= 0 || r > N - 1) return;
        if (go[l][r] == -1) {
            ans[l - 1] = '(';
            ans[r - 1] = ')';
            get_answer (l + 1, r - 1);
        } else {
            ans[l - 1] = '(';
            ans[go[l][r] - 1] = ')';
            ans[go[l][r]] = '(';
            ans[r - 1] = ')';
            get_answer (l + 1, go[l][r] - 1);
            get_answer (go[l][r] + 2, r - 1);
        }
    };
    get_answer (1, N - 1);
    cout << ans << "\n";
}

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