제출 #589199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
589199		andrei_boaca	괄호 문자열 (CEOI16_match)	C++14	100 / 100	218 ms	263144 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;
set<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]].insert(i);
    }
    set<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.begin();
            int par=1-i%2;
            int lit=s[i]-'a'+1;
            auto it=prev(mypoz[lit][par][sum[i-1]].lower_bound(maxpoz));
            int poz=(*it);
            sol[poz]=')';
            last.insert(poz);
            //mypoz[lit][par][sum[i-1]].erase(it);
        }
        else
            last.erase(i);
    }
    for(int i=1;i<=n;i++)
        cout<<sol[i];
    return 0;
}

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