Submission #589203

#	Time	Username	Problem	Language	Result	Execution time	Memory
589203		andrei_boaca	Match (CEOI16_match)	C++14	100 / 100	118 ms	133068 KiB

match

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const ll baza=29,invbaza=758620695;
const ll mod=1e9+7;
int n;
string s,sol;
vector<char> st;
vector<int> mypoz[27][2][100005];
map<ll,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();
        else
            st.push_back(s[i]);
    }
    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=(h*invbaza)%mod;
        }
        else
        {
            h=((h*baza)%mod+s[i]-'a'+1)%mod;
            st.push_back(s[i]);
        }
        if(nrm[h]==0)
        {
            nr++;
            nrm[h]=nr;
        }
        sum[i]=nrm[h];
        mypoz[s[i]-'a'+1][i%2][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[lit][par][sum[i-1]].size();
            rgt--;
            int poz=0;
            while(lft<=rgt)
            {
                int mij=(lft+rgt)/2;
                if(mypoz[lit][par][sum[i-1]][mij]<maxpoz)
                {
                    poz=mypoz[lit][par][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;
}

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