Submission #53089

#	Time	Username	Problem	Language	Result	Execution time	Memory
53089		Diuven	Match (CEOI16_match)	C++11	100 / 100	20 ms	13500 KiB

match

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=2e9;

int n;
char S[MX], R[MX];

int P[MX][30];
void init(){
    for(int j=0; j<='z'-'a'; j++)
        P[1][j]=0;

    for(int i=2; i<=n; i++){
        for(int j=0; j<='z'-'a'; j++){
            if(S[i]-'a'==j) P[i][j]=i;
            else{
                int k=P[i-1][S[i]-'a'];
                if(k<=1) P[i][j]=0;
                else P[i][j]=P[k-1][j];
            }
        }
    }
}

bool solve(int s, int e){
    if(e<=s) return e<s;
    int m=P[e][S[s]-'a'];
    if(m<=s) return false;
    R[s]='('; R[m]=')';
    return solve(s+1,m-1)&&solve(m+1,e);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>(S+1);
    for(int i=1; S[i]!=0; i++) n=i;

    init();

    if(!solve(1,n)){
        cout<<-1;
        return 0;
    }
    cout<<(R+1);
    return 0;
}

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