제출 #129023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129023		davitmarg	괄호 문자열 (CEOI16_match)	C++17	100 / 100	105 ms	17872 KiB

match

/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

LL binpow(LL a,LL n)
{
	if(n==0)
		return 1;
	if(n%2==0)
        return binpow((a*a)%mod,n/2);
    return (a*binpow(a,n-1))%mod;
}

LL inv(LL x)
{
	return binpow(x,mod-2);
}

LL h[100005],pr=7919,a=1;
int p[100005][30],lst[30];
int n;
string s,ans;
vector<int> st;
map<LL,vector<int>> used;

void dfs(int l,int r)
{
	if(l>r)
		return;
	if(s[l]==s[r])
	{
        ans[l]='(';
        ans[r]=')';
		//cout<<"! "<<ans<<endl;
        dfs(l+1,r-1);
		return;
	}
    int m=p[r][s[l]-'a'];
    dfs(l,m);
    dfs(m+1,r);
}

int main()
{
    cin>>s;
    n=s.length();
    s="#"+s;
    ans=s;
    for(int i=1;i<=n;i++)
		if(!st.empty() && s[st.back()]==s[i])
		{
            h[i]=(h[i-1]+mod-((s[st.back()]-'a'+1ll)*a)%mod)%mod;
            a*=inv(pr);
            a%=mod;
            st.pop_back();
		}
		else
		{
			st.PB(i);
			a*=pr;
			a%=mod;
            h[i]=(h[i-1]+((s[i]-'a'+1ll)*a)%mod)%mod;
		}

    if(!st.empty())
	{
		cout<<-1<<endl;
        return 0;
	}
    for(int i=0;i<=n;i++)
		used[h[i]].PB(i);

    for(auto it=used.begin();it!=used.end();++it)
	{
        for(int j=0;j<26;j++)
			lst[j]=0;
        vector<int> x=it->second;
        for(int i=0;i<x.size();i++)
		{
			for(int j=0;j<26;j++)
				if(lst[j]!=-1)
					p[x[i]][j]=lst[j];
			//cout<<"!! "<<x[i]<<" "<<s[x[i]]<<endl;
            lst[s[x[i]]-'a']=x[i];
		}
	}

	dfs(1,n);
    for(int i=1;i<=n;i++)
		printf("%c",ans[i]);
	cout<<endl;
	return 0;
}


/*



bcabccddeffebgabccddeffebggagacddeffeb
cabccddeffebgabccddeffebggagacddeffe


*/

컴파일 시 표준 에러 (stderr) 메시지

match.cpp: In function 'int main()':
match.cpp:98:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<x.size();i++)
                     ~^~~~~~~~~

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