oj.uz

Submission #223627

# Submission time Handle Problem Language Result Execution time Memory
223627 2020-04-15T20:40:32 Z MKopchev Match (CEOI16_match) C++14
0 / 100
 9 ms 10496 KB 
#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;

int n;
string inp;

char output[nmax];

int prev_pos[nmax][26];

void solve(int l,int r)
{
    if(l>r)return;

    int mid=prev_pos[r][inp[l]-'a'];

    if(l>=mid)
    {
        cout<<-1<<endl;
        exit(0);
    }

    output[l]='(';
    output[mid]=')';

    solve(l+1,mid-1);

    solve(mid+1,r);
}
int main()
{
    cin>>inp;
    n=inp.size();

    memset(prev_pos,-1,sizeof(prev_pos));

    for(int i=1;i<=n;i++)
        for(int j=0;j<26;j++)
    {
        if(inp[i]==j+'a')prev_pos[i][j]=i;
        else if(prev_pos[i-1][j]!=-1)prev_pos[i][j]=prev_pos[prev_pos[i-1][inp[i]-'a']-1][j];
    }

    solve(0,n-1);

    for(int i=0;i<n;i++)
        cout<<output[i];

    cout<<endl;
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 63.0

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