oj.uz

Submission #608446

# Submission time Handle Problem Language Result Execution time Memory
608446 2022-07-27T07:40:45 Z BJoozz Match (CEOI16_match) C++14
100 / 100
 35 ms 37676 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;
    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;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2900 KB Output is correct
2 Correct 1 ms 2900 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2900 KB Output is correct
2 Correct 1 ms 2900 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct

Subtask #3
63.0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2900 KB Output is correct
2 Correct 1 ms 2900 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 3156 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 3 ms 3540 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 5332 KB Output is correct
10 Correct 3 ms 5332 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 20 ms 23892 KB Output is correct
13 Correct 22 ms 25660 KB Output is correct
14 Correct 26 ms 27476 KB Output is correct
15 Correct 26 ms 31020 KB Output is correct
16 Correct 35 ms 30964 KB Output is correct
17 Correct 25 ms 32716 KB Output is correct
18 Correct 35 ms 34336 KB Output is correct
19 Correct 31 ms 36048 KB Output is correct
20 Correct 20 ms 23928 KB Output is correct
21 Correct 31 ms 37676 KB Output is correct