oj.uz

Submission #53068

# Submission time Handle Problem Language Result Execution time Memory
53068 2018-06-28T03:56:01 Z Diuven Match (CEOI16_match) C++11
10 / 100
 3 ms 716 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=2e9;

int n;

char S[MX], R[MX];

int P[MX][30];
void init(){
    for(int j=0; j<='z'-'a'; j++)
        P[1][j]=0;

    for(int i=2; i<=n; i++){
        for(int j=0; j<='z'-'a'; j++){
            if(S[i-1]==S[i]){
                if(i-2<1) P[i][j]=0;
                else if(S[i-2]==j+'a') P[i][j]=i-2;
                else P[i][j]=P[i-2][j];
            }
            else{
                int k=P[i-1][S[i]-'a'];
                if(k<=1) P[i][j]=0;
                else P[i][j]=P[k-1][j];
            }
        }
    }
}

bool solve(int s, int e){
    if(e<=s) return e<s;
    if(S[s]==S[e]){
        R[s]='('; R[e]=')';
        return solve(s+1, e-1);
    }
    int m=P[e][S[s]-'a'];
    if(m<s) return false;
    R[s]=R[m+1]='(';
    R[m]=R[e]=')';
    return solve(s,m)&&solve(m+1,e);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>(S+1);
    for(int i=1; S[i]!=0; i++) n=i;

    init();

    if(!solve(1,n)){
        cout<<-1;
        return 0;
    }
    cout<<(R+1);
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Incorrect 2 ms 716 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 408 KB Output is correct
4 Incorrect 2 ms 716 KB Output isn't correct
5 Halted 0 ms 0 KB -