제출 #608446

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
608446		BJoozz	Match (CEOI16_match)	C++14	100 / 100	35 ms	37676 KiB

match

#define X first
#define Y second
#define pb push_back
#include<bits/stdc++.h>
using namespace std;

#define int long long
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int randint(int l,int r){
    return uniform_int_distribution < int > (l,r) (rng);
}
typedef pair < int , int > ii;
using ll = long long;
using ld = long double;
const int MAX=1e5+5,inf=1e16,mod=1e9+7;
template <class X, class Y>
bool cmax(X &a, const Y &b) {
    return a < b ? a = b, 1 : 0;
}
template <class X, class Y>
bool cmin(X &a, const Y &b) {
    return a > b ? a = b, 1 : 0;
}
void maxx(int &a,int b){if(b>a)a=b;}
void minn(int &a,int b){if(b<a)a=b;}
//ii C[MAX],R[MAX];
//int a[MAX][MAX];
vector < int > pr[MAX];
int a[MAX];
char st[MAX];
int ST[26][MAX];
int SS[26][MAX];
int S[MAX],T[MAX];
int pa[17][MAX];
bool vs[MAX];
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("MATCH.inp","r",stdin);freopen("MATCH.out","w",stdout);
    int n;
    cin>>st+1;
    n=strlen(st+1);
    for(int j=0;j<26;j++) SS[j][n+1]=n+1;
    for(int j=0;j<17;j++)pa[j][n+1]=n+1;
    for(int i=n,x;i>0;i--){
        x=st[i]-'a';
        S[i]=SS[x][i+1];
        //T[i]=ST[x][i+1];
        pa[0][i]=S[i]+1;
        if(S[i]>n) pa[0][i]=n+1;
        for(int j=0;j<26;j++) {
            SS[j][i]=SS[j][pa[0][i]];
            //ST[j][i]=ST[j][S[i]+1];
        }
        for(int j=1;j<17;j++) pa[j][i]=pa[j-1][pa[j-1][i]];
        SS[x][i]=i;
        //cout<<S[i]<<'\n';
        //if(!ST[x][i]) ST[x][i]=i;
    }
    string ans;
    stack < int > sta;
    sta.push(n+1);
    for(int i=1;i<=n;i++)if(!vs[i]){
        int x=st[i]-'a',u=i+1;
        for(int j=16;j>=0;j--) if(SS[x][pa[j][u]]<sta.top())u=pa[j][u];
        vs[u]=1;
        ans+='(';

        //cout<<SS[x][u]<<'\n';
        if(SS[x][u]>=sta.top()){
            cout<<-1;return 0;
        }
        sta.push(u);
        //cout<<i<<' '<<u<<' '<<SS[x][u]<<'\n';
    }else {
        ans+=')';sta.pop();
    }
    cout<<ans;
}

컴파일 시 표준 에러 (stderr) 메시지

match.cpp: In function 'int main()':
match.cpp:41:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     cin>>st+1;
      |          ~~^~

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