Submission #259431

#	Time	Username	Problem	Language	Result	Execution time	Memory
259431		doowey	Match (CEOI16_match)	C++14	100 / 100	72 ms	70136 KiB

match

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int AL = 26;
const int N = (int)1e5 + 10;
const int T = (int)1e5 + 10;
int nx[T][AL];
char fs[N];
int shis[N];
int par[N];

int cnt = 1;

int root[N];
vector<int> P[T][AL];
char sol[N];

void compute(int l, int r){
    if(l > r) return;
    int ix = root[l - 1];
    int cv = shis[l];
    int it = upper_bound(P[ix][cv].begin(), P[ix][cv].end(), r) - P[ix][cv].begin();
    it -- ;
    int id = P[ix][cv][it];
    if(id > l && id <= r){
        sol[l]='(';
        sol[id]=')';
        compute(l+1, id-1);
        compute(id+1, r);
    }
    else{
        cout << "bad\n";
        return;
    }
}


int main(){
    fastIO;
    string t;
    cin >> t;
    int n = t.size();
    char f;
    int id;
    fs[1] = '#';
    root[0] = 1;
    for(int i = 1; i <= n; i ++ ){
        f = t[i - 1];
        id = f - 'a';
        shis[i]=id;
        if(f == fs[root[i - 1]]){
            root[i] = par[root[i-1]];
        }
        else{
            root[i] = root[i - 1];
            if(nx[root[i]][id] == 0){
                nx[root[i]][id] = ++cnt;
                par[cnt] = root[i];
                fs[cnt] = f;
            }
            root[i] = nx[root[i]][id];
        }
        P[root[i]][id].push_back(i);
    }
    if(root[n] != 1){
        cout << "-1\n";
        return 0;
    }
    compute(1, n);
    for(int i = 1; i <= n; i ++ )
        cout << sol[i];
    return 0;
}

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