Submission #531854

#	Time	Username	Problem	Language	Result	Execution time	Memory
531854		thiago_bastos	Palindromes (APIO14_palindrome)	C++17	0 / 100	211 ms	17248 KiB

palindrome

#include "bits/stdc++.h"

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using i32 = int;
using u32 = unsigned;
using i16 = short;
using u16 = unsigned short;
using ld = long double;
using ii = pair<int, int>;

const int mod[2] = {67557961, 1'000'000'009};
const int base[2] = {3468547, 752747959};

struct Hash {
	vector<int> h[2], pt[2];
	int n;
	Hash() {}
	Hash(string& s) {
		n = s.size();
		for(int i = 0; i < 2; ++i) {
			h[i].resize(n + 1);
			pt[i].resize(n + 1);
			h[i][0] = 0, pt[i][0] = 1;
			for(int j = 1; j <= n; ++j) {
				pt[i][j] = (i64)pt[i][j - 1] * base[i] % mod[i];
				h[i][j] = (h[i][j - 1] + pt[i][j] * (s[j - 1] - 'a' + 1ll)) % mod[i];
			}
		}
	}
	int hash(int k, int l, int r) {
		i64 x = h[k][r] - h[k][l - 1];
		if(x < 0) x += mod[k];
		return x * pt[k][n - l] % mod[k];
	}
	ii hash(int l, int r) {
		++l, ++r;
		return ii(hash(0, l, r), hash(1, l, r));
	}
};

string s;
int l, r, n;
Hash h;
vector<int> d1, d2;

i64 f(int m) {
	map<ii, int> cnt;
	i64 ans = 0;
	if(m & 1) {
		for(int i = 0; i < n; ++i) {
			if(2 * d1[i] + 1 < m) continue;
			ans = max(ans, ++cnt[h.hash(i - d1[i], i + d1[i])] * (i64)m);
		}
	} else {
		for(int i = 0, k; i < n; ++i) {
			if(2 * d2[i] < m) continue;
			ans = max(ans, ++cnt[h.hash(i - d2[i], i + d2[i] - 1)] * (i64)m);
		}
	}
	return ans;
}

void solve() {
	
	cin >> s;
	
	h = Hash(s);
	l = 0, r = -1, n = s.size();
	d1.assign(n, 1);
	d2.assign(n, 0);

	for(int i = 0; i < n; ++i) {
		if(i <= r) {
			d1[i] = min(d1[l + r - i], r - i + 1);
			d2[i] = min(d2[l + r - i + 1], r - i + 1);
		}
		while(i + d1[i] < n && i - d1[i] >= 0 && s[i - d1[i]] == s[i + d1[i]]) ++d1[i];
		while(i + d2[i] < n && i - d2[i] - 1 >= 0 && s[i - d2[i] - 1] == s[i + d2[i]]) ++d2[i];
		if(r < i + d2[i] - 1) l = i - d2[i], r = i + d2[i] - 1;
		if(r < i + d1[i] - 1) l = i - d1[i] + 1, r = i + d1[i] - 1;
	}
	
	l = 1, r = n;

	while(l < r) {
		int mid = (l + r) / 2;
		if(f(mid) > f(mid + 1)) r = mid;
		else l = mid + 1;		
	}

	cout << f(r) << '\n';
}

int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) solve();
 	return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'i64 f(int)':
palindrome.cpp:58:18: warning: unused variable 'k' [-Wunused-variable]
   58 |   for(int i = 0, k; i < n; ++i) {
      |                  ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27