oj.uz

Submission #5940

# Submission time Handle Problem Language Result Execution time Memory
5940 2014-05-31T14:41:06 Z tncks0121 Palindromes (APIO14_palindrome) C++
73 / 100
 276 ms 76968 KB 
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  
#include <time.h>

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 300005, lgN_ = 19;
char S[N_]; int N;

int SA[N_], CP[lgN_][N_+N_];
int start[N_], lnk[N_], temp[N_];

int RMQ[lgN_][N_];
int lg2[N_];

void build_suffix_array() {
	for(int i = 1; i <= N; i++) SA[i] = i, CP[0][i] = S[i] - 'a' + 1;
	for(int k = 0; k+1 < lgN_; k++) {
		for(int c = 1; c >= 0; c--) {
			for(int i = N; i > 0; i--) {
				int x = SA[i] + (c<<k); if(x > N) x = 0;
				int v = CP[k][x];
				lnk[i] = start[v]; start[v] = i;
				temp[i] = SA[i];
			}
			for(int i = 0, p = 0; i <= N || i <= 26; i++) { 
				for(int j = start[i]; j > 0; j = lnk[j]) SA[++p] = temp[j];
				start[i] = -1;
			}
		}
		
		int *now = CP[k], *nxt = CP[k+1];
		nxt[SA[1]] = 1;
		for(int i = 2, v = 1; i <= N; i++) {
			int ap = now[SA[i-1]], bp = now[SA[i]];
			int an = (SA[i-1] + (1<<k) <= N) ? now[SA[i-1] + (1<<k)] : 0;
			int bn = (SA[i] + (1<<k) <= N) ? now[SA[i] + (1<<k)] : 0;
			if(ap < bp || (ap == bp && an < bn)) ++v;
			nxt[SA[i]] = v;
		}
	}
}

int lcp_logn (int x, int y) {
	int r = 0;
	if(x == y) return N-x+1;
	for(int k = lgN_; --k >= 0; ) {
		if(CP[k][x+r] == CP[k][y+r]) r += 1<<k;
	}
	return r;
}

void build_lcp () {
	for(int i = 1; i < N; i++) RMQ[0][i] = lcp_logn(SA[i], SA[i+1]);
	for(int i = 1, v = 0; i <= N; i++) v += (i>>v), lg2[i] = v-1;

	for(int k = 1; k < lgN_; k++) {
		for(int i = 1; i + (1<<k) - 1 <= N - 1; i++) RMQ[k][i] = min(RMQ[k-1][i], RMQ[k-1][i + (1<<(k-1))]);
	}
}

int lcp_constant (int x, int y) {
	if(x == y) return N-x+1;

	x = CP[lgN_-1][x]; y = CP[lgN_-1][y];
	if(x > y) swap(x, y);
	int l = y-x; int k = lg2[l];

	//printf("%d %d: %d: %d\n", x, y, l, 1<<k);
	return min(RMQ[k][x], RMQ[k][y-(1<<k)]);
}

int num_occurance (int x, int y) { // S[x..|S|]∞˙¿? √÷¿?∞???¡??Œª? ±?¿?∞° y-x+1 ¿?ª?¿?∏? ??
	int w = CP[lgN_-1][x];
	int low, high, ret1 = 0, ret2 = 0;

	for(low = 1, high = w-1; low <= high; ) {
		int mid = (low + high) >> 1;
		if(lcp_constant(x, SA[mid]) >= y-x+1) {
			ret1 = w - mid;
			high = mid - 1;
		}else {
			low = mid + 1;
		}
	}

	for(low = w+1, high = N; low <= high; ) {
		int mid = (low + high) >> 1;
		if(lcp_constant(x, SA[mid]) >= y-x+1) {
			ret2 = mid - w;
			low = mid + 1;
		}else {
			high = mid - 1;
		}
	}

	return ret1 + ret2 + 1;
}

char T[N_+N_]; int TN;	

int Table[N_+N_];

ll res;

int main() {
	scanf("%s", S+1); N = strlen(S+1);

	build_suffix_array();
	build_lcp();

	T[++TN] = '.';
	for(int i = 1; i <= N; i++) T[++TN] = S[i], T[++TN] = '.';

	int pr = -1, pm = -1;
	for(int i = 1; i <= TN; i++) {
		int &t = Table[i];
		if(i <= pr) t = min(Table[pm + pm - i], pr - i);
		while(i-t > 0 && i+t <= TN && T[i-t] == T[i+t]) {
			if(pr < i+t) pr = i+t, pm = i;
			if((i + t) % 2 == 0) res = max(res, (ll)(t + 1) * num_occurance((i - t) / 2, (i + t) / 2));
			++t;
		}
		--t;
	}

	printf("%lld\n", res);

	return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 76968 KB Output is correct - answer is '1249925001'
2 Correct 80 ms 76968 KB Output is correct - answer is '396337935'
3 Correct 72 ms 76968 KB Output is correct - answer is '2500050000'
4 Correct 92 ms 76968 KB Output is correct - answer is '1016525689'
5 Correct 200 ms 76968 KB Output is correct - answer is '99645'
6 Correct 176 ms 76968 KB Output is correct - answer is '78569380'
7 Correct 112 ms 76968 KB Output is correct - answer is '82810000'
8 Correct 244 ms 76968 KB Output is correct - answer is '3989'
9 Correct 196 ms 76968 KB Output is correct - answer is '125529616'
10 Correct 216 ms 76968 KB Output is correct - answer is '66664'

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 276 ms 76968 KB Output isn't correct - expected '11250075000', found '14268250128'
2 Halted 0 ms 0 KB -