oj.uz

Submission #231425

# Submission time Handle Problem Language Result Execution time Memory
231425 2020-05-13T15:13:41 Z nicolaalexandra Match (CEOI16_match) C++14
10 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
char v[DIM],sol[DIM],s[DIM];
int poz[DIM][30];
int n,i,j;

void solve (int st, int dr){
    /// in st pun ( si trb sa gasesc )
    if (st >= dr)
        return;
    if (st == dr-1){
        sol[st] = '(';
        sol[dr] = ')';
        return;
    }

    /*for (i=dr;i>st;--i){ /// aparent asta a mers bine in practica
        if (!k && v[i] == v[st])
            break;
        if (k && s[k] == v[i])
            k--;
        else s[++k] = v[i];
    }*/

    sol[st] = '(';
    int idx = poz[dr][v[st]-'a'];
    sol[idx] = ')';

    solve (st+1,idx-1);
    solve (idx+1,dr);
}

int main (){

    //ifstream cin ("match.in");
    //ofstream cout ("match.out");

    cin>>v+1;
    n = strlen (v+1);

    /// verific daca am solutie
    int k = 0;
    s[++k] = v[1];
    for (i=2;i<=n;++i){
        if (k && s[k] == v[i])
            k--;
        else s[++k] = v[i];
    }

    if (k){
        cout<<-1<<"\n";
        return 0;
    }

    for (i=1;i<=n;i++)
        for (j=0;j<26;j++){
            if (v[i] - 'a' == j)
                poz[i][j] = i;
            else poz[i][j] = poz[i-1][j];
        }

    solve (1,n);

    cout<<sol+1<<"\n";


    return 0;
}

Compilation message

match.cpp: In function 'int main()':
match.cpp:39:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin>>v+1;
          ~^~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 63.0

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