oj.uz

Submission #13454

# Submission time Handle Problem Language Result Execution time Memory
13454 2015-02-21T03:08:42 Z ainta Palindromes (APIO14_palindrome) C++
100 / 100
 974 ms 70816 KB 
#include<stdio.h>
#include<algorithm>
#define N_ 300010
#define N2_ 600010
#define SZ 524288
using namespace std;
char p[N2_];
int LCP[N2_][20], SA[N2_], Num[N2_], po[N2_];
struct Arr{
	int a, b;
}Li[N2_];
int n, m, C[N2_], ord[N2_], ord2[N2_];
void Suffix_Array(){
	int i, L = 1, M, cnt;
	for (i = 1; i <= m; i++){
		Li[i].a = p[i], Li[i].b = 0;
	}
	while (1){
		M = max(m, 256);
		for (i = 1; i <= m; i++)C[Li[i].b]++;
		for (i = 1; i <= M; i++)C[i] += C[i - 1];
		for (i = 1; i <= m; i++)ord[C[Li[i].b]--] = i;
		for (i = 0; i <= M; i++)C[i] = 0;
		for (i = 1; i <= m; i++)C[Li[i].a]++;
		for (i = 1; i <= M; i++)C[i] += C[i - 1];
		for (i = m; i >= 1; i--)ord2[C[Li[ord[i]].a]--] = ord[i];
		for (i = 0; i <= M; i++)C[i] = 0;
		cnt = 0;
		for (i = 1; i <= m; i++){
			if (i == 1 || Li[ord2[i]].a != Li[ord2[i - 1]].a || Li[ord2[i]].b != Li[ord2[i - 1]].b)cnt++;
			SA[ord2[i]] = cnt;
		}
		if (L >= m)break;
		for (i = 1; i <= m; i++){
			Li[i].a = SA[i];
			if (i + L > m)Li[i].b = 0;
			else Li[i].b = SA[i + L];
		}
		L *= 2;
	}
	for (i = 1; i <= m; i++)Num[SA[i]] = i;
}
void Make_LCP(){
	int i, L = 0, x, j;
	for (i = 1; i <= m; i++){
		if (SA[i] == m)continue;
		if (L)L--;
		x = Num[SA[i] + 1];
		while (p[i + L] == p[x + L])L++;
		LCP[SA[i]][0] = L;
	}
	for (i = 0; i < 19; i++){
		for (j = 1; j <= m; j++){
			if (j + (1 << i) <= m) LCP[j][i + 1] = min(LCP[j][i], LCP[j + (1 << i)][i]);
		}
	}
}
int get_LCP(int b, int e){
	if (b>e)return get_LCP(e, b);
	int d = po[e - b];
	return min(LCP[b][d], LCP[e - (1 << d)][d]);
}
int w[N2_], S[N_];
long long Res;
void Do(int ck){
	int i, L = 0, j, Sum;
	for (i = 1; i <= m + 1; i++){
		Sum = 0;
		while (L > LCP[i - 1][0]){
			Sum += S[L];
			S[L] = 0;
			Res = max(Res, (long long)Sum * (L * 2 - ck));
			L--;
		}
		if (i == m + 1)break;
		S[L] += Sum;
		L = max(L, w[i]);
		S[w[i]]++;
	}
}
int main(){
	int i;
	scanf("%s", p + 1);
	for (i = 1; p[i]; i++);
	n = i - 1;
	m = n + n + 1;
	p[n + 1] = ' ';
	for (i = 1; i <= n; i++)p[m + 1 - i] = p[i];
	Suffix_Array();
	Make_LCP();
	for (i = 1; i <= m; i++){
		po[i] = po[i - 1];
		if ((1 << (po[i] + 1)) == i)po[i]++;
	}
	for (i = 1; i <= n; i++)w[SA[i]] = get_LCP(SA[i], SA[m + 1 - i]);
	Do(1);
	w[SA[1]] = 0;
	for (i = 2; i <= n; i++)w[SA[i]] = get_LCP(SA[i], SA[m + 2 - i]);
	Do(0);
	printf("%lld\n", Res);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 70816 KB Output is correct - answer is '7'
2 Correct 0 ms 70816 KB Output is correct - answer is '4'
3 Correct 0 ms 70816 KB Output is correct - answer is '9'
4 Correct 0 ms 70816 KB Output is correct - answer is '1'
5 Correct 0 ms 70816 KB Output is correct - answer is '1'
6 Correct 0 ms 70816 KB Output is correct - answer is '2'
7 Correct 0 ms 70816 KB Output is correct - answer is '3'
8 Correct 0 ms 70816 KB Output is correct - answer is '3'
9 Correct 0 ms 70816 KB Output is correct - answer is '15'
10 Correct 0 ms 70816 KB Output is correct - answer is '24'
11 Correct 0 ms 70816 KB Output is correct - answer is '10'
12 Correct 0 ms 70816 KB Output is correct - answer is '24'
13 Correct 0 ms 70816 KB Output is correct - answer is '25'
14 Correct 0 ms 70816 KB Output is correct - answer is '28'
15 Correct 0 ms 70816 KB Output is correct - answer is '2'
16 Correct 0 ms 70816 KB Output is correct - answer is '1'
17 Correct 0 ms 70816 KB Output is correct - answer is '15'
18 Correct 0 ms 70816 KB Output is correct - answer is '18'
19 Correct 0 ms 70816 KB Output is correct - answer is '1176'
20 Correct 0 ms 70816 KB Output is correct - answer is '1225'
21 Correct 2 ms 70816 KB Output is correct - answer is '136'
22 Correct 0 ms 70816 KB Output is correct - answer is '45'
23 Correct 0 ms 70816 KB Output is correct - answer is '2500'
24 Correct 0 ms 70816 KB Output is correct - answer is '380'
25 Correct 2 ms 70816 KB Output is correct - answer is '2304'
26 Correct 0 ms 70816 KB Output is correct - answer is '110'
27 Correct 0 ms 70816 KB Output is correct - answer is '93'
28 Correct 0 ms 70816 KB Output is correct - answer is '729'
29 Correct 0 ms 70816 KB Output is correct - answer is '132'
30 Correct 0 ms 70816 KB Output is correct - answer is '7'
31 Correct 0 ms 70816 KB Output is correct - answer is '8'
32 Correct 0 ms 70816 KB Output is correct - answer is '64'

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 70816 KB Output is correct - answer is '124251'
2 Correct 0 ms 70816 KB Output is correct - answer is '38226'
3 Correct 0 ms 70816 KB Output is correct - answer is '249500'
4 Correct 3 ms 70816 KB Output is correct - answer is '5778'
5 Correct 3 ms 70816 KB Output is correct - answer is '247506'
6 Correct 0 ms 70816 KB Output is correct - answer is '248004'
7 Correct 0 ms 70816 KB Output is correct - answer is '973'
8 Correct 3 ms 70816 KB Output is correct - answer is '123753'
9 Correct 0 ms 70816 KB Output is correct - answer is '2346'
10 Correct 0 ms 70816 KB Output is correct - answer is '53'
11 Correct 3 ms 70816 KB Output is correct - answer is '52'
12 Correct 0 ms 70816 KB Output is correct - answer is '976'

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 70816 KB Output is correct - answer is '12497500'
2 Correct 12 ms 70816 KB Output is correct - answer is '6481800'
3 Correct 8 ms 70816 KB Output is correct - answer is '25000000'
4 Correct 4 ms 70816 KB Output is correct - answer is '17816841'
5 Correct 14 ms 70816 KB Output is correct - answer is '9945'
6 Correct 9 ms 70816 KB Output is correct - answer is '504100'
7 Correct 6 ms 70816 KB Output is correct - answer is '1512930'
8 Correct 12 ms 70816 KB Output is correct - answer is '413'
9 Correct 16 ms 70816 KB Output is correct - answer is '428'
10 Correct 10 ms 70816 KB Output is correct - answer is '7232'

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 70816 KB Output is correct - answer is '1249925001'
2 Correct 127 ms 70816 KB Output is correct - answer is '396337935'
3 Correct 130 ms 70816 KB Output is correct - answer is '2500050000'
4 Correct 130 ms 70816 KB Output is correct - answer is '1016525689'
5 Correct 196 ms 70816 KB Output is correct - answer is '99645'
6 Correct 180 ms 70816 KB Output is correct - answer is '78569380'
7 Correct 153 ms 70816 KB Output is correct - answer is '82810000'
8 Correct 257 ms 70816 KB Output is correct - answer is '3989'
9 Correct 229 ms 70816 KB Output is correct - answer is '125529616'
10 Correct 191 ms 70816 KB Output is correct - answer is '66664'

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 443 ms 70816 KB Output is correct - answer is '11250075000'
2 Correct 446 ms 70816 KB Output is correct - answer is '894243195'
3 Correct 450 ms 70816 KB Output is correct - answer is '22499400004'
4 Correct 460 ms 70816 KB Output is correct - answer is '2958163321'
5 Correct 690 ms 70816 KB Output is correct - answer is '298935'
6 Correct 546 ms 70816 KB Output is correct - answer is '1210831209'
7 Correct 555 ms 70816 KB Output is correct - answer is '303195156'
8 Correct 974 ms 70816 KB Output is correct - answer is '11804'
9 Correct 961 ms 70816 KB Output is correct - answer is '11813'
10 Correct 685 ms 70816 KB Output is correct - answer is '262144'
11 Correct 470 ms 70816 KB Output is correct - answer is '3750025000'
12 Correct 918 ms 70816 KB Output is correct - answer is '184796836'