oj.uz

Submission #7620

# Submission time Handle Problem Language Result Execution time Memory
7620 2014-08-13T05:52:00 Z myungwoo Palindromes (APIO14_palindrome) C++
100 / 100
 580 ms 55728 KB 
#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 300005
typedef long long lld;

int N;
int R[MAXN*2],SA[MAXN],pos[MAXN],lcp[MAXN],P[MAXN][19],Q[MAXN][19];
lld ans;
char A[MAXN*2];

void Manachers()
{
	int r = 0, p = 0;
	for (int i=1;i<=N;i++){
		if (i <= r) R[i] = min(R[2*p-i],r-i);
		else R[i] = 0;
		while (i > R[i] && i+R[i]+1 <= N && A[i-R[i]-1] == A[i+R[i]+1]) R[i]++;
		if (r < i+R[i]) r = i+R[i], p = i;
	}
}

void SuffixArray()
{
	int i,j,k;
	int m = 27;
	vector <int> cnt(max(N,m)+1,0),x(N+1,0),y(N+1,0);
	for (i=1;i<=N;i++) cnt[x[i] = (A[i]=='#')?27:A[i]-'a'+1]++;
	for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
	for (i=N;i;i--) SA[cnt[x[i]]--] = i;
	for (int len=1,p=1;p<N;len<<=1,m=p){
		for (p=0,i=N-len;++i<=N;) y[++p] = i;
		for (i=1;i<=N;i++) if (SA[i] > len) y[++p] = SA[i]-len;
		for (i=0;i<=m;i++) cnt[i] = 0;
		for (i=1;i<=N;i++) cnt[x[y[i]]]++;
		for (i=1;i<=m;i++) cnt[i] += cnt[i-1];
		for (i=N;i;i--) SA[cnt[x[y[i]]]--] = y[i];
		swap(x,y); p = 1; x[SA[1]] = 1;
		for (i=1;i<N;i++)
			x[SA[i+1]] = SA[i]+len <= N && SA[i+1]+len <= N && y[SA[i]] == y[SA[i+1]] && y[SA[i]+len] == y[SA[i+1]+len] ? p : ++p;
	}
}

void LCP()
{
	int i,j,k=0;
	vector <int> rank(N+1,0);
	for (i=1;i<=N;i++) rank[SA[i]] = i;
	for (i=1;i<=N;lcp[rank[i++]]=k)
		for (k?k--:0,j=SA[rank[i]-1];A[i+k]==A[j+k];k++);
	for (i=2;i<=N;i++) P[i][0] = Q[i][0] = lcp[i];
	for (j=0;j<18;j++){
		for (i=2;i<=N;i++){
			P[i][j+1] = (i+(1<<j)<=N?min(P[i][j],P[i+(1<<j)][j]):0);
			Q[i][j+1] = (i-(1<<j)>1?min(Q[i][j],Q[i-(1<<j)][j]):0);
		}
	}
}

void proc(int a,int b)
{
	int i;
	int len=b-a+1, cnt=1;
	int q = pos[a], p = q+1;
	for (i=19;i--;){
		if (Q[q][i] >= len) q -= (1<<i), cnt += (1<<i);
		if (P[p][i] >= len) p += (1<<i), cnt += (1<<i);
	}
	ans = max(ans,(lld)len*cnt);
}

int main()
{
	int i,j;
	scanf("%s",A+1); N = strlen(A+1);
	SuffixArray(); LCP();
	for (i=1;i<=N;i++) pos[SA[i]] = i;
	for (i=N;i;i--) A[i+i-1] = A[i]; N = N+N-1;
	for (i=2;i<N;i+=2) A[i] = '#';
	Manachers();
	for (i=1,j=0;i<=N;i++){
		while (j+1 <= i+R[i]){
			j++;
			if (A[j] == '#') continue;
			proc((i+i-j)/2+1,j/2+1);
		}
	}
	printf("%lld\n",ans);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 53388 KB Output is correct - answer is '1249925001'
2 Correct 64 ms 53388 KB Output is correct - answer is '396337935'
3 Correct 68 ms 53388 KB Output is correct - answer is '2500050000'
4 Correct 72 ms 53388 KB Output is correct - answer is '1016525689'
5 Correct 92 ms 53388 KB Output is correct - answer is '99645'
6 Correct 92 ms 53388 KB Output is correct - answer is '78569380'
7 Correct 76 ms 53388 KB Output is correct - answer is '82810000'
8 Correct 88 ms 53388 KB Output is correct - answer is '3989'
9 Correct 112 ms 53388 KB Output is correct - answer is '125529616'
10 Correct 92 ms 53388 KB Output is correct - answer is '66664'

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 55728 KB Output is correct - answer is '11250075000'
2 Correct 236 ms 55728 KB Output is correct - answer is '894243195'
3 Correct 236 ms 55728 KB Output is correct - answer is '22499400004'
4 Correct 224 ms 55728 KB Output is correct - answer is '2958163321'
5 Correct 364 ms 55728 KB Output is correct - answer is '298935'
6 Correct 260 ms 55728 KB Output is correct - answer is '1210831209'
7 Correct 252 ms 55728 KB Output is correct - answer is '303195156'
8 Correct 328 ms 55728 KB Output is correct - answer is '11804'
9 Correct 344 ms 55728 KB Output is correct - answer is '11813'
10 Correct 348 ms 55728 KB Output is correct - answer is '262144'
11 Correct 240 ms 55728 KB Output is correct - answer is '3750025000'
12 Correct 580 ms 55728 KB Output is correct - answer is '184796836'