Submission #609733

#TimeUsernameProblemLanguageResultExecution timeMemory
609733KrisjanisPMatch (CEOI16_match)C++17
100 / 100
15 ms25264 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...