Submission #53068

#	Time	Username	Problem	Language	Result	Execution time	Memory
53068		Diuven	Match (CEOI16_match)	C++11	10 / 100	3 ms	716 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-1]==S[i]){
                if(i-2<1) P[i][j]=0;
                else if(S[i-2]==j+'a') P[i][j]=i-2;
                else P[i][j]=P[i-2][j];
            }
            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;
    if(S[s]==S[e]){
        R[s]='('; R[e]=')';
        return solve(s+1, e-1);
    }
    int m=P[e][S[s]-'a'];
    if(m<s) return false;
    R[s]=R[m+1]='(';
    R[m]=R[e]=')';
    return solve(s,m)&&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: 0 / 27
• Subtask 3: 0 / 63