Submission #231434

#	Time	Username	Problem	Language	Result	Execution time	Memory
231434		nicolaalexandra	Match (CEOI16_match)	C++14	100 / 100	22 ms	13688 KiB

match

#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 (poz[i-1][v[i]-'a'])
                poz[i][j] = poz[poz[i-1][v[i]-'a']-1][j];
        }
        poz[i][v[i]-'a'] = i;
    }

    solve (1,n);

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


    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 63 / 63