oj.uz

Submission #5526

# Submission time Handle Problem Language Result Execution time Memory
5526 2014-05-05T12:37:34 Z ainta Palindromes (APIO14_palindrome) C++
100 / 100
 760 ms 59388 KB 
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#include<stdlib.h>
#define N_ 300010
#define SZ 524288
using namespace std;
int D[N_ * 2], n, ord[20][N_], LCP[20][N_], C, Count[N_];
long long Res;
char p[N_], q[N_ * 2];
struct A{
	int a, b, num;
	bool operator <(const A &p)const{
		return a != p.a ? a<p.a : b<p.b;
	}
}w[N_], tw[N_];
void Do(int b, int e){
	int L = e - b + 1, t = ord[C][b], be = t, ed = t, i;
	for (i = C; i >= 0; i--){
		if (LCP[i][ed] >= L)ed += (1 << i);
	}
	for (i = C; i >= 0; i--){
		if (be >= (1<<i) && LCP[i][be - (1<<i)] >= L)be -= (1 << i);
	}
	Res = max(Res, (long long)(ed - be + 1)*L);
}
void DP(){
	int i, M = -1, mid, m;
	for (i = 0; p[i]; i++){
		q[i * 2] = p[i];
		q[i * 2 + 1] = '-';
	}
	m = n * 2 - 1;
	for (i = 0; i<m; i++){
		if (M >= i){
			if (D[mid * 2 - i] < M - i){
				D[i] = D[mid * 2 - i];
				continue;
			}
		}
		mid = i;
		while (M + 1 < m && M + 1 <= i * 2 && q[M + 1] == q[i * 2 - M - 1]){
			M++;
			if (M % 2 == 0){
				Do((i * 2 - M) / 2, M / 2);
			}
		}
		D[i] = M - i;
	}
}
void SA(){
	int i, K = 1, cnt, M = 'z';
	for (i = 0; p[i]; i++){
		tw[i].a = p[i], tw[i].b = 0, tw[i].num = i;
	}
	n = i;
	while (1){
		for (i = 0; i < n; i++){
			Count[tw[i].a]++;
		}
		for (i = 1; i <= M; i++)Count[i] += Count[i - 1];
		for (i = n - 1; i >= 0; i--){
			w[--Count[tw[i].a]] = tw[i];
		}
		for (i = 1; i <= M; i++)Count[i] = 0;
		cnt = 0;
		for (i = 0; i<n; i++){
			if (!i || w[i].a != w[i - 1].a || w[i].b != w[i - 1].b)cnt++;
			ord[C][w[i].num] = cnt;
		}
		if (K >= n) break;
		M = cnt;
		cnt = n - 1;
		for (i = n - 1; i >= 0; i--){
			if (w[i].num < K)continue;
			tw[cnt].a = ord[C][w[i].num - K];
			tw[cnt].b = ord[C][w[i].num];
			tw[cnt--].num = w[i].num - K;
		}
		for (i = n - K; i < n; i++){
			tw[cnt].a = ord[C][i];
			tw[cnt].b = 0;
			tw[cnt--].num = i;
		}
		K *= 2;
		C++;
	}
}
int Gap(int a, int b){
	int i, r = 0;
	for (i = C; i >= 0; i--){
		if (ord[i][a] == ord[i][b]){
			a += (1 << i);
			b += (1 << i);
			r += (1 << i);
		}
	}
	return r;
}
void PrePro(){
	int i, j;
	for (i = 0; i < n - 1; i++){
		LCP[0][i+1] = Gap(w[i].num, w[i + 1].num);
	}
	for (i = 0; i < C; i++){
		for (j = 1; j < n - (1 << i); j++){
			LCP[i + 1][j] = min(LCP[i][j], LCP[i][j + (1 << i)]);
		}
	}
}
int main()
{
	scanf("%s", p);
	SA();
	PrePro();
	DP();
	printf("%lld\n", Res);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 59388 KB Output is correct - answer is '1249925001'
2 Correct 56 ms 59388 KB Output is correct - answer is '396337935'
3 Correct 48 ms 59388 KB Output is correct - answer is '2500050000'
4 Correct 52 ms 59388 KB Output is correct - answer is '1016525689'
5 Correct 132 ms 59388 KB Output is correct - answer is '99645'
6 Correct 120 ms 59388 KB Output is correct - answer is '78569380'
7 Correct 72 ms 59388 KB Output is correct - answer is '82810000'
8 Correct 160 ms 59388 KB Output is correct - answer is '3989'
9 Correct 124 ms 59388 KB Output is correct - answer is '125529616'
10 Correct 144 ms 59388 KB Output is correct - answer is '66664'

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 59388 KB Output is correct - answer is '11250075000'
2 Correct 200 ms 59388 KB Output is correct - answer is '894243195'
3 Correct 176 ms 59388 KB Output is correct - answer is '22499400004'
4 Correct 176 ms 59388 KB Output is correct - answer is '2958163321'
5 Correct 740 ms 59388 KB Output is correct - answer is '298935'
6 Correct 288 ms 59388 KB Output is correct - answer is '1210831209'
7 Correct 328 ms 59388 KB Output is correct - answer is '303195156'
8 Correct 756 ms 59388 KB Output is correct - answer is '11804'
9 Correct 724 ms 59388 KB Output is correct - answer is '11813'
10 Correct 760 ms 59388 KB Output is correct - answer is '262144'
11 Correct 184 ms 59388 KB Output is correct - answer is '3750025000'
12 Correct 680 ms 59388 KB Output is correct - answer is '184796836'