제출 #608736

#제출 시각아이디문제언어결과실행 시간메모리
608736PyqeMatch (CEOI16_match)C++17
100 / 100
41 ms39116 KiB
#include <bits/stdc++.h>

using namespace std;

const long long ma=26;
long long n,nn=0,nn2=0,a[100069],sk[100069],sk2[100069];

struct trie
{
	vector<long long> vl[ma];
	trie *p[ma],*pr;
	
	void bd()
	{
		long long i;
		
		for(i=0;i<ma;i++)
		{
			p[i]=0;
		}
		pr=0;
	}
}
tr,*ptr[100069];

int main()
{
	long long i,k,l,p;
	string s;
	
	cin>>s;
	n=s.length();
	tr.bd();
	ptr[0]=&tr;
	for(i=1;i<=n;i++)
	{
		a[i]=s[i-1]-'a';
		if(!nn||a[i]!=sk[nn])
		{
			nn++;
			sk[nn]=a[i];
			if(!ptr[i-1]->p[a[i]])
			{
				ptr[i-1]->p[a[i]]=new trie;
				ptr[i-1]->p[a[i]]->bd();
				ptr[i-1]->p[a[i]]->pr=ptr[i-1];
			}
			ptr[i]=ptr[i-1]->p[a[i]];
		}
		else
		{
			nn--;
			ptr[i]=ptr[i-1]->pr;
		}
		ptr[i]->vl[a[i]].push_back(i);
	}
	if(nn)
	{
		printf("-1\n");
		return 0;
	}
	sk2[0]=n+1;
	for(i=1;i<=n;i++)
	{
		k=sk2[nn2];
		p=upper_bound(ptr[k-1]->vl[a[i]].begin(),ptr[k-1]->vl[a[i]].end(),k-1)-ptr[k-1]->vl[a[i]].begin()-1;
		l=-1;
		if(p>=0)
		{
			l=ptr[k-1]->vl[a[i]][p];
		}
		if(l>i)
		{
			nn2++;
			sk2[nn2]=l;
			printf("(");
			continue;
		}
		nn2--;
		printf(")");
	}
	printf("\n");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...