Submission #589227

#TimeUsernameProblemLanguageResultExecution timeMemory
589227andrei_boacaMatch (CEOI16_match)C++14
100 / 100
66 ms55792 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int baza=29,invbaza=758620695;
const int mod=1e9+7;
int n;
string s,sol;
vector<char> st;
vector<vector<int>> mypoz[2][27];
unordered_map<int,int> nrm;
int nxt[100005];
int sum[100005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    n=s.size();
    s=" "+s;
    if(n%2==1)
    {
        cout<<-1;
        return 0;
    }
    int nr=1;
    ll h=0;
    nrm[h]=1;
    sum[0]=1;
    for(int i=1;i<=n;i++)
    {
        if(!st.empty()&&st.back()==s[i])
        {
            st.pop_back();
            h-=(s[i]-'a'+1);
            h=(1LL*h*invbaza)%mod;
        }
        else
        {
            h=((1LL*h*baza)+s[i]-'a'+1)%mod;
            st.push_back(s[i]);
        }
        if(nrm[h]==0)
        {
            nr++;
            nrm[h]=nr;
        }
        sum[i]=nrm[h];
    }
    for(int i=1;i<=26;i++)
        for(int j=0;j<=1;j++)
            mypoz[j][i].resize(nr+1);
    if(!st.empty())
    {
        cout<<-1;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st.empty()&&st.back()==s[i])
        {
            st.pop_back();
            h-=(s[i]-'a'+1);
            h=(1LL*h*invbaza)%mod;
        }
        else
        {
            h=((1LL*h*baza)+s[i]-'a'+1)%mod;
            st.push_back(s[i]);
        }
        if(nrm[h]==0)
        {
            nr++;
            nrm[h]=nr;
        }
        sum[i]=nrm[h];
        mypoz[i%2][s[i]-'a'+1][sum[i]].push_back(i);
    }
    vector<int> last;
    sol.resize(n+1);
    for(int i=1;i<=n;i++)
    {
        if(sol[i]!=')')
        {
            sol[i]='(';
            int maxpoz=n+1;
            if(!last.empty())
                maxpoz=last.back();
            int par=1-i%2;
            int lit=s[i]-'a'+1;
            int lft=0;
            int rgt=mypoz[par][lit][sum[i-1]].size();
            rgt--;
            int poz=0;
            while(lft<=rgt)
            {
                int mij=(lft+rgt)/2;
                if(mypoz[par][lit][sum[i-1]][mij]<maxpoz)
                {
                    poz=mypoz[par][lit][sum[i-1]][mij];
                    lft=mij+1;
                }
                else
                    rgt=mij-1;
            }
            sol[poz]=')';
            last.push_back(poz);
        }
        else
            last.pop_back();
    }
    for(int i=1;i<=n;i++)
        cout<<sol[i];
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...