Submission #225352

#	Time	Username	Problem	Language	Result	Execution time	Memory
225352		brcode	Match (CEOI16_match)	C++14	100 / 100	39 ms	13432 KiB

match

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
   string s;
   int dp[MAXN][30];
   char ans[MAXN];
void solve(int l,int r){
    if(l>r){
        return;
    }
    int mid = dp[r][s[l]-'a'];
    if(l>=mid){
        cout<<-1<<endl;
        exit(0);
    }
    ans[l] = '(';
    ans[mid] = ')';
    solve(l+1,mid-1);
    solve(mid+1,r);
}
int main() {
 
    cin>>s;
    int n = s.length();
    for(int i=0;i<n;i++){
        for(int j=0;j<26;j++){
            if(s[i]==j+'a'){
                dp[i][j] = i;
            }else if(i && dp[i-1][s[i]-'a']>0){
                dp[i][j] = dp[dp[i-1][s[i]-'a']-1][j];
            }
        }
    }
    solve(0,n-1);
    for(int i=0;i<n;i++){
        cout<<ans[i];
    }
}

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