oj.uz

Submission #7609

# Submission time Handle Problem Language Result Execution time Memory
7609 2014-08-12T13:44:24 Z hongjun7 Palindromes (APIO14_palindrome) C++
100 / 100
 796 ms 61732 KB 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MK 21
#define MN 300005
int n, cnt, ord[MK][MN], lcp[MK][MN], K, sc[MN], dyn[MN<<1];
char _S[MN], S[MN*2];
long long res;
struct data {
	int a, b, x;
	bool operator < (const data p) const {
		if (a == p.a) return b < p.b;
		return a < p.a;
	}
} w[MN], v[MN];
void upd(int a, int b) {
	int L = b-a+1, t = ord[K][a], lo = t, hi = t;
	for (int i = K; i >= 0; i--) {
		if (lo >= (1<<i) && lcp[i][lo-(1<<i)] >= L) lo -= (1<<i);
		if (lcp[i][hi] >= L) hi += (1<<i);
	}
	res = max(res, (long long)(hi-lo+1)*L);
}
int main() {
	int i, j;
	scanf("%s",_S);
	n = strlen(_S);
	int k = 1, M = 'z';
	for (i = 0; i < n; i++) v[i].a = _S[i], v[i].b = 0, v[i].x = i;
	while (1) {
		for (i = 0; i <= n-1; i++) sc[v[i].a]++;
		for (i = 1; i <= M; i++) sc[i] += sc[i-1];
		for (i = n-1; i >= 0; i--) w[--sc[v[i].a]] = v[i];
		for (i = 1; i <= M; i++) sc[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[K][w[i].x] = cnt;
		}
		if (k >= n) break;
		M = cnt; cnt = n-1;
		for (i = n-1; i >= 0; i--) {
			if (w[i].x < k) continue;
			v[cnt].a = ord[K][w[i].x-k], v[cnt].b = ord[K][w[i].x], v[cnt--].x = w[i].x-k;
		}
		for (i = n-k; i < n; i++) v[cnt].a = ord[K][i], v[cnt].b = 0, v[cnt--].x = i;
		k<<=1;
		K++;
	}
	for (i = 1; i < n; i++) {
		int w1 = w[i-1].x, w2 = w[i].x;
		for (j = K; j >= 0; j--) if (ord[j][w1] == ord[j][w2]) w1 += (1<<j), w2 += (1<<j), lcp[0][i] += (1<<j);
	}
	for (i = 0; i < K; i++) for (j = 1; j < n-(1<<i); j++) lcp[i+1][j] = min(lcp[i][j], lcp[i][j+(1<<i)]);
	for (i = 0; _S[i]; i++) S[i*2] = _S[i], S[i*2+1] = '-';
	int m = n*2-1;
	M = -1;
	for (i = 0; i < m; i++) {
		if (i <= M && dyn[j*2-i] <= M-i-1) { dyn[i] = dyn[j*2-i]; continue; }
		j = i;
		while (M+1 < m && M+1 <= i*2 && S[M+1] == S[i*2-(M+1)]) {
			M++;
			if (M&1) continue;
			upd((i*2-M)/2, M/2);
		}
		dyn[i] = M-i;
	}
	printf("%lld", res);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 61732 KB Output is correct - answer is '1249925001'
2 Correct 56 ms 61732 KB Output is correct - answer is '396337935'
3 Correct 48 ms 61732 KB Output is correct - answer is '2500050000'
4 Correct 44 ms 61732 KB Output is correct - answer is '1016525689'
5 Correct 132 ms 61732 KB Output is correct - answer is '99645'
6 Correct 108 ms 61732 KB Output is correct - answer is '78569380'
7 Correct 68 ms 61732 KB Output is correct - answer is '82810000'
8 Correct 136 ms 61732 KB Output is correct - answer is '3989'
9 Correct 116 ms 61732 KB Output is correct - answer is '125529616'
10 Correct 140 ms 61732 KB Output is correct - answer is '66664'

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 61732 KB Output is correct - answer is '11250075000'
2 Correct 184 ms 61732 KB Output is correct - answer is '894243195'
3 Correct 168 ms 61732 KB Output is correct - answer is '22499400004'
4 Correct 168 ms 61732 KB Output is correct - answer is '2958163321'
5 Correct 768 ms 61732 KB Output is correct - answer is '298935'
6 Correct 324 ms 61732 KB Output is correct - answer is '1210831209'
7 Correct 304 ms 61732 KB Output is correct - answer is '303195156'
8 Correct 732 ms 61732 KB Output is correct - answer is '11804'
9 Correct 700 ms 61732 KB Output is correct - answer is '11813'
10 Correct 796 ms 61732 KB Output is correct - answer is '262144'
11 Correct 192 ms 61732 KB Output is correct - answer is '3750025000'
12 Correct 628 ms 61732 KB Output is correct - answer is '184796836'