Submission #608736

#	Time	Username	Problem	Language	Result	Execution time	Memory
608736		Pyqe	Match (CEOI16_match)	C++17	100 / 100	41 ms	39116 KiB

match

#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");
}

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