oj.uz

Submission #134932

# Submission time Handle Problem Language Result Execution time Memory
134932 2019-07-23T12:37:12 Z wilwxk Palindromes (APIO14_palindrome) C++14
0 / 100
 42 ms 7700 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=3e5+5;
const ll MOD=1e9+9;
const ll P=257;
char c[MAXN];
ll h[MAXN], rh[MAXN];
ll pot[MAXN];
int n;
ll respf=0;

ll ghash(int ini, int fim) {
	ll val=0;
	if(ini<=fim) {
		if(ini!=0) val=h[ini-1];
		val*=pot[fim-ini+1]; val%=MOD;
		val=h[fim]-val;
		while(val<0) val+=MOD;
	}
	else {
		if(ini!=n-1) val=rh[ini+1];
		val*=pot[ini-fim+1]; val%=MOD;
		val=rh[fim]-val;
		while(val<0) val+=MOD;
	}
	return val;
}

ll testa(int k) {
	if(k<=0||k>n) return 0;
	int resp=0;
	// printf("testing %d\n", k);
	unordered_map<ll, int> mp;
	for(int i=k-1; i<n; i++) {
		int ind=i-k+1;
		ll val=ghash(ind, i);
		// printf("  %d: %lld %lld\n", i, val, ghash(i, ind));
		if(val==ghash(i, ind)) {
			mp[val]++;
			resp=max(resp, mp[val]);
		}
	}
	// printf("testa %d >> %d\n", k, resp);
	return (ll)resp*k;
}

void precalc() {
	pot[0]=1;
	for(int i=1; i<=n; i++) pot[i]=(pot[i-1]*P)%MOD;
	for(int i=0; i<n; i++) {
		if(i!=0) h[i]=(h[i-1]*P)%MOD;
		h[i]+=(c[i]-'a'); h[i]%=MOD;
	}
	for(int i=n-1; i>=0; i--) {
		if(i!=n-1) rh[i]=(rh[i+1]*P)%MOD;
		rh[i]+=(c[i]-'a'); rh[i]%=MOD;
	}
}

int main() {
	scanf(" %s", c); n=strlen(c);
	precalc();

	// for(int i=1; i<=n; i++) respf=max(respf, testa(i));

	int opt=0;
	for(int i=n; i>0; i/=2) {
		// printf("tenta add %d\n", i);
		while(opt+i<n&&(testa(opt+i)<=testa(opt+i+1)||testa(opt+i+1)<=testa(opt+i+2))) {
			opt+=i;
		}
	}
	respf=max(testa(opt), testa(opt+2));
	respf=max(respf, testa(opt+1));
	respf=max(respf, testa(opt-1));
	respf=max(respf, testa(opt-2));

	printf("%lld\n", respf);
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", c); n=strlen(c);
  ~~~~~^~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 7700 KB Output isn't correct
2 Halted 0 ms 0 KB -