Submission #609733

#	Time	Username	Problem	Language	Result	Execution time	Memory
609733		KrisjanisP	Match (CEOI16_match)	C++17	100 / 100	15 ms	25264 KiB

match

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

string str, res;
const ll N = 1e5;
bool prevPos_visited[N][27];
ll prevPos_result[N][27];
bool bad = false;
ll prevPos(ll i, ll c)
{
    if(i<=0)
    {
        bad = true;
        return -1;
    }
    if((str[i]-'a')==c) return i;
    if(prevPos_visited[i][c])
        return prevPos_result[i][c];
    prevPos_visited[i][c] = 1;
    prevPos_result[i][c] = prevPos(prevPos(i-1,str[i]-'a')-1,c);
    return prevPos_result[i][c];
}

void construct(ll i, ll j)
{
    ll k;
    if((j-i)%2==0) bad=true;
    else k = prevPos(j,str[i]-'a');
    if(bad) return;
    res[i] = '(', res[k]=')';
    if(k-i>1)
        construct(i+1,k-1);
    if(k!=j)
        construct(k+1,j);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>str;
    ll n = str.size();
    res = str;
    construct(0,n-1);
    if(!bad)
        cout<<res<<"\n";
    else
        cout<<"-1\n";
}

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