Submission #341636

#	Time	Username	Problem	Language	Result	Execution time	Memory
341636		phathnv	Match (CEOI16_match)	C++11	100 / 100	20 ms	12648 KiB

match

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e5 + 1;
const int AL = 26;

int n, match[N], pre[N][AL];
char answer[N];
string s;

void readInput(){
    cin >> s;
    n = s.size();
    s = '*' + s;
}

void process(int l, int r){
    if (l > r)
        return;
    int p = pre[r][s[l] - 'a'];
    if (!p){
        cout << -1;
        exit(0);
    }
    answer[l] = '(';
    answer[p] = ')';
    process(l + 1, p - 1);
    process(p + 1, r);
}

void solve(){
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < AL; j++)
            if (s[i] - 'a' == j)
                pre[i][j] = i;
            else
                pre[i][j] = pre[max(0, pre[i - 1][s[i] - 'a'] - 1)][j];
    process(1, n);
    for(int i = 1; i <= n; i++)
        cout << answer[i];
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    readInput();
    solve();
    return 0;
}

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