oj.uz

답안 #608736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
608736 2022-07-27T09:48:16 Z Pyqe 괄호 문자열 (CEOI16_match) C++17
100 / 100
 41 ms 39116 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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