oj.uz

Submission #8511

# Submission time Handle Problem Language Result Execution time Memory
8511 2014-09-15T06:08:31 Z cki86201 Palindromes (APIO14_palindrome) C++
100 / 100
 804 ms 34780 KB 
#include<stdio.h>
#include<algorithm>

#define N_ 300030
#define LN 20

char ch[N_];
int N;
int SA[N_], RA[N_], tRA[N_], C[N_], tSA[N_];
int LCP[N_][LN], iSA[N_];
char S[N_<<1];
int P[N_<<1];
long long ans;

int main(){
	scanf("%s",ch);
	while(ch[++N]);
	int i, cnt = 128;
	for(i=0;i<N;i++)SA[i] = i, RA[i] = ch[i];
	for(int L=1;L<N;L<<=1){
		for(i=0;i<N;i++)++C[i+L < N ? RA[i+L] : 0];
		for(i=1;i<=cnt;i++)C[i] += C[i-1];
		for(i=N-1;i>=0;i--)tSA[--C[i+L < N ? RA[i+L] : 0]] = i;
		for(i=0;i<=cnt;i++)C[i] = 0;
		for(i=0;i<N;i++)++C[RA[i]];
		for(i=1;i<=cnt;i++)C[i] += C[i-1];
		for(i=N-1;i>=0;i--)SA[--C[RA[tSA[i]]]] = tSA[i];
		for(i=0;i<=cnt;i++)C[i] = 0;
		for(i=0,cnt=1;i<N;i++){
			if(i!=0 && (RA[SA[i]] != RA[SA[i-1]] || (SA[i]+L<N?RA[SA[i]+L]:0) != (SA[i]+L<N?RA[SA[i-1]+L]:0)))cnt++;
			tRA[i] = cnt;
		}
		for(i=0;i<N;i++)RA[SA[i]] = tRA[i];
	}
	for(i=0;i<N;i++)iSA[SA[i]] = i;
	int L;
	for(i=0,L=0;i<N;LCP[iSA[i++]][0] = L, L = (L?L-1:0)){
		if(iSA[i] == 0)continue;
		while(ch[i+L] == ch[SA[iSA[i]-1]+L])L++;
	}
	for(i=0;i<N;i++)
		for(int j=1;j<LN;j++){
			if(i < (1<<j))break;
			LCP[i][j] = std::min(LCP[i][j-1], LCP[i-(1<<(j-1))][j-1]);
		}
	for(i=0;i<N;i++)S[i<<1] = ch[i], S[i<<1|1] = '#';
	int M = N+N-1, c = -1, r;
	for(i=0;i<M;i++){
		if(i <= c && P[r+r-i] < c-i)P[i] = P[r+r-i];
		else{
			r = i;
			while(c+1 < M && c < i+i && S[c+1] == S[i+i-c-1]){
				if(c++ & 1){
					int rr = iSA[(i+i-c)>>1], ll = rr, len = c-i+1;
					for(int j=LN-1;j>=0;j--)if(rr+(1<<j) < N && LCP[rr+(1<<j)][j] >= len)rr += 1<<j;
					for(int j=LN-1;j>=0;j--)if(LCP[ll][j] >= len){
						ll -= 1<<j;
					}
					ans = std::max(ans, (long long)(rr - ll + 1) * len);
				}
			}
			P[i] = c-i;
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 34780 KB Output is correct - answer is '1249925001'
2 Correct 72 ms 34780 KB Output is correct - answer is '396337935'
3 Correct 84 ms 34780 KB Output is correct - answer is '2500050000'
4 Correct 68 ms 34780 KB Output is correct - answer is '1016525689'
5 Correct 128 ms 34780 KB Output is correct - answer is '99645'
6 Correct 104 ms 34780 KB Output is correct - answer is '78569380'
7 Correct 84 ms 34780 KB Output is correct - answer is '82810000'
8 Correct 160 ms 34780 KB Output is correct - answer is '3989'
9 Correct 132 ms 34780 KB Output is correct - answer is '125529616'
10 Correct 116 ms 34780 KB Output is correct - answer is '66664'

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 34780 KB Output is correct - answer is '11250075000'
2 Correct 220 ms 34780 KB Output is correct - answer is '894243195'
3 Correct 288 ms 34780 KB Output is correct - answer is '22499400004'
4 Correct 252 ms 34780 KB Output is correct - answer is '2958163321'
5 Correct 632 ms 34780 KB Output is correct - answer is '298935'
6 Correct 320 ms 34780 KB Output is correct - answer is '1210831209'
7 Correct 324 ms 34780 KB Output is correct - answer is '303195156'
8 Correct 804 ms 34780 KB Output is correct - answer is '11804'
9 Correct 800 ms 34780 KB Output is correct - answer is '11813'
10 Correct 628 ms 34780 KB Output is correct - answer is '262144'
11 Correct 208 ms 34780 KB Output is correct - answer is '3750025000'
12 Correct 708 ms 34780 KB Output is correct - answer is '184796836'