Submission #506987

#	Time	Username	Problem	Language	Result	Execution time	Memory
506987		CyberSleeper	Match (CEOI16_match)	C++14	100 / 100	13 ms	14796 KiB

match

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define all(x)      x.begin(), x.end()
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ull         unsigned long long
#define pll         pair<ll, ll>
#define ld          long double
#define nl          '\n'
#define tb          '\t'
#define sp          ' '
using namespace std;

const ll MX=100005, MOD=1e9+7, BLOCK=327, INF=2e9+7;
const ll INFF=4e18+7;

const ld ERR=1e-7, pi=3.14159265358979323846;

string S, ans;
int N, bef[MX][28];

bool cek(){
    vector<int> vec;
    for(int i=0; i<N; i++){
        if(vec.size() && S[i]==S[vec.back()]){
            vec.pop_back();
        }else{
            vec.pb(i);
        }
    }
    return vec.empty();
}
void rec(int le, int ri){
    if(ri<le)
        return;
    int mi=bef[ri][S[le]-'a'];
    ans.pb('(');
    rec(le+1, mi-1);
    ans.pb(')');
    rec(mi+1, ri);
}

int main(){
    fastio;
    cin >> S;
    N=S.size();
    if(!cek()){
        cout << "-1\n";
        return 0;
    }
    memset(bef, -1, sizeof(bef));
    bef[0][S[0]-'a']=0;
    for(int i=1; i<N; i++){
        for(int j=0, now; j<26; j++){
            if((S[i]-'a')==j)
                bef[i][j]=i;
            else{
                now=bef[i-1][S[i]-'a'];
                if(now>0)
                    bef[i][j]=bef[now-1][j];
            }
        }
    }
    rec(0, N-1);
    cout << ans << nl;
}

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