Submission #231420

#	Time	Username	Problem	Language	Result	Execution time	Memory
231420		nicolaalexandra	Match (CEOI16_match)	C++14	37 / 100	2089 ms	24696 KiB

match

#include <bits/stdc++.h>
#define DIM 100010
using namespace std;
char v[DIM],sol[DIM];
deque <char> s,d;
int n,i;

int verif (int poz){
    for (int i=poz;i<=n;i++){
        if (!d.empty() && d.back() == v[i])
            d.pop_back();
        else d.push_back(v[i]);
    }
    return d.empty();
}


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;
    }

    sol[st] = '(';
    int val = v[st] - 'a';
    int i;
    deque <char> s;
    for (i=dr;i>st;i--){
        if (s.empty() && v[i] == v[st])
            break;
        if (!s.empty() && s.back() == v[i])
            s.pop_back();
        else s.push_back(v[i]);
    }

    sol[i] = ')';
    solve (st+1,i-1);
    solve (i+1,dr);
}

int main (){

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

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

    /// verific daca am solutie
    s.push_back(v[1]);
    for (i=2;i<=n;i++){
        if (!s.empty() && s.back() == v[i])
            s.pop_back();
        else s.push_back(v[i]);
    }

    if (!s.empty()){
        cout<<-1;
        return 0;
    }

    /*for (i=1;i<=n;i++)
        poz[v[i]-'a'].push_back(i);

    for (i=0;i<26;i++)
        reverse (poz[i].begin(),poz[i].end());*/

    solve (1,n);

    for (i=1;i<=n;i++)
        cout<<sol[i];

    return 0;
}

Compilation message (stderr)

match.cpp: In function 'void solve(int, int)':
match.cpp:29:9: warning: unused variable 'val' [-Wunused-variable]
     int val = v[st] - 'a';
         ^~~
match.cpp: In function 'int main()':
match.cpp:50:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin>>v+1;
          ~^~

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