Submission #26638

#	Time	Username	Problem	Language	Result	Execution time	Memory
26638		yutaka1999	Match (CEOI16_match)	C++14	100 / 100	23 ms	21688 KiB

match

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#define SIZE 100005
#define M1 1000000007LL
#define B1 89793LL
#define M2 1000000009LL
#define B2 799923LL
#define ALP 30

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> PL;
typedef pair <PL,int> PLL;

char A[SIZE];
int to[SIZE];
int st[SIZE];
int back[SIZE][ALP];
PL ht[SIZE];
ll r1[SIZE],r2[SIZE];
char ans[SIZE];
int n;

void calc()
{
	r1[0]=r2[0]=1;
	for(int i=1;i<SIZE;i++)
	{
		r1[i]=r1[i-1]*B1%M1;
		r2[i]=r2[i-1]*B2%M2;
	}
	int sz=0;
	ll h1=0,h2=0;
	for(int i=n-1;i>=0;i--)
	{
		if(sz>0&&A[st[sz-1]]==A[i])
		{
			sz--;
			h1-=(ll) (A[i]-'a'+1)*r1[sz]%M1;
			if(h1<0) h1+=M1;
			h2-=(ll) (A[i]-'a'+1)*r2[sz]%M2;
			if(h2<0) h2+=M2;
		}
		else
		{
			st[sz]=i;
			h1+=(ll) (A[i]-'a'+1)*r1[sz]%M1;
			if(h1>=M1) h1-=M1;
			h2+=(ll) (A[i]-'a'+1)*r2[sz]%M2;
			if(h2>=M2) h2-=M2;
			sz++;
		}
		ht[i]=PL(h1,h2);
	}
	vector <PLL> vx;
	for(int i=0;i<n;i++) vx.push_back(PLL(ht[i],i));
	vx.push_back(PLL(PL(0,0),n));
	sort(vx.begin(),vx.end());
	memset(to,-1,sizeof(to));
	for(int i=0;i<vx.size();)
	{
		int f=i;
		int bef=-1;
		for(;i<vx.size()&&vx[i].first==vx[f].first;i++)
		{
			to[vx[i].second-1]=bef;
			bef=vx[i].second;
		}
	}
}
int main()
{
	scanf("%s",&A);
	n=strlen(A);
	calc();
	int now=n-1;
	while(now>=0)
	{
		if(to[now]==-1) break;
		now=to[now]-1;
	}
	if(now!=-1)
	{
		puts("-1");
		return 0;
	}
	//for(int i=0;i<n;i++) printf("%d ",to[i]);puts("");
	memset(back,-1,sizeof(back));
	for(int i=0;i<n;i++)
	{
		if(to[i]>0)
		{
			for(int j=0;j<ALP;j++)
			{
				if(to[i]==0) back[i][j]=-1;
				else back[i][j]=back[to[i]-1][j];
			}
		}
		back[i][A[i]-'a']=i;
		//printf("%d : %d %d\n",i,back[i][0],back[i][1]);
	}
	int sz=0;
	st[sz++]=n;
	for(int i=0;i<n;i++)
	{
		if(st[sz-1]==i)
		{
			//(
			printf(")");
			sz--;
		}
		else
		{
			printf("(");//)
			int to=back[st[sz-1]-1][A[i]-'a'];
			//printf("%d %d\n",i,to);
			st[sz++]=to;
		}
	}
	puts("");
	return 0;
}

Compilation message (stderr)

match.cpp: In function 'void calc()':
match.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<vx.size();)
               ^
match.cpp:67:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(;i<vx.size()&&vx[i].first==vx[f].first;i++)
         ^
match.cpp: In function 'int main()':
match.cpp:76:15: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[100005]' [-Wformat=]
  scanf("%s",&A);
               ^
match.cpp:76:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s",&A);
                ^

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