Submission #608736

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
608736	2022-07-27T09:48:16 Z	Pyqe	Match (CEOI16_match)	C++17	100 / 100	41 ms	39116 KB

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	496 KB	Output is correct
5	Correct	1 ms	724 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct

Subtask #3

63.0 / 63.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	496 KB	Output is correct
5	Correct	1 ms	724 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	596 KB	Output is correct
8	Correct	2 ms	2132 KB	Output is correct
9	Correct	4 ms	2672 KB	Output is correct
10	Correct	3 ms	3284 KB	Output is correct
11	Correct	3 ms	3272 KB	Output is correct
12	Correct	25 ms	27132 KB	Output is correct
13	Correct	26 ms	29516 KB	Output is correct
14	Correct	30 ms	30956 KB	Output is correct
15	Correct	9 ms	3244 KB	Output is correct
16	Correct	9 ms	3156 KB	Output is correct
17	Correct	27 ms	21192 KB	Output is correct
18	Correct	13 ms	3520 KB	Output is correct
19	Correct	40 ms	39116 KB	Output is correct
20	Correct	28 ms	27248 KB	Output is correct
21	Correct	41 ms	38180 KB	Output is correct