oj.uz

Submission #608425

# Submission time Handle Problem Language Result Execution time Memory
608425 2022-07-27T07:34:23 Z BJoozz Match (CEOI16_match) C++14
0 / 100
 2 ms 2900 KB 
#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;
    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]]<=n)
        u=pa[j][u];
        vs[u]=1;
        ans+='(';
        if(SS[x][u]>n){
            cout<<-1;return 0;
        }
        //cout<<i<<' '<<u<<' '<<SS[x][u]<<'\n';
    }else ans+=')';
    cout<<ans;
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Incorrect 2 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Incorrect 2 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Incorrect 2 ms 2900 KB Output isn't correct
3 Halted 0 ms 0 KB -