Submission #223587

#	Time	Username	Problem	Language	Result	Execution time	Memory
223587		MKopchev	Match (CEOI16_match)	C++14	37 / 100	2089 ms	772 KiB

match

#include<bits/stdc++.h>
using namespace std;

const int nmax=1e5+42;

int n;
string inp;

string outp;

stack<int> active,mem;

bool check(int pos)
{
    while(pos<n)
    {
        if(active.size()==0)active.push(pos);
        else if(inp[active.top()]==inp[pos])active.pop();
        else active.push(pos);
        pos++;
    }
    return active.size()==0;
}
int main()
{
    cin>>inp;
    n=inp.size();

    if(check(0)==0)
    {
        printf("-1\n");
        return 0;
    }

    for(int i=0;i<n;i++)
    {
        mem=active;
        active.push(i);

        bool possible=check(i+1);

        active=mem;

        if(possible)
        {
            outp.push_back('(');
            active.push(i);
        }
        else
        {
            outp.push_back(')');
            active.pop();
        }
    }

    cout<<outp<<endl;
    return 0;
}

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