Submission #716686

#	Time	Username	Problem	Language	Result	Execution time	Memory
716686		thiago_bastos	Palindromes (APIO14_palindrome)	C++17	73 / 100	1071 ms	48252 KiB

palindrome

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("mmx,sse,sse2,sse3,sse4,sse4.1,sse4.2,avx")
#include "bits/stdc++.h"

using namespace std;
 
#define INF   1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
 
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;
using i128 = __int128;

struct Hash {
	static const i64 P;
	static i64 B;
	vector<i64> pw, h;

	i64 mul(i64 a, i64 b) {
		i128 c = (i128)a * b;
		c = (c & P) + (c >> 61);
		if(c >= P) c -= P;
		return c;
	}

	i64 sum(i64 a, i64 b) {
		a += b;
		if(a >= P) a -= P;
		return a;
	}

	Hash(string& s) {
		int n = s.size();
		pw.resize(n + 1);
		h.resize(n + 1);
		pw[0] = 1;
		h[0] = 0;
		for(int i = 1; i <= n; ++i) {
			pw[i] = mul(pw[i - 1], B);
			h[i] = sum(h[i - 1], mul(pw[i], s[i - 1]));
		}
	}

	i64 operator()(int l, int r) {
		int n = pw.size();
		return mul(pw[n-l-1], sum(h[r+1], P - h[l]));
	}
};

mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());
 
i64 uniform(i64 l, i64 r) {
	uniform_int_distribution<i64> uid(l, r);
	return uid(rng);
}

const i64 Hash :: P = (1ll << 61) - 1;
i64 Hash :: B = uniform(256, (1ll << 61) - 2);

i64 f(string& s) {
	string t(rall(s));
	Hash hs(s), ht(t);
	using T = pair<int, i64>;
	map<T, int, greater<T>> mp;
	map<i64, ii> interval;

	int n = s.size();
	
	for(int i = 0; i < n; ++i) {
		ii st[] = {{i, i}, {i, i + 1}};
		for(auto [l, r] : st) {
			if(s[l] != s[r]) continue;
			int lo = 0, hi = min(l, n - r - 1) + 1;
			while(lo < hi) {
				int m = (lo + hi) / 2;
				i64 h1 = hs(l - m, l);
				i64 h2 = ht(n - r - m - 1, n - r - 1);
				if(h1 != h2) hi = m;
				else lo = m + 1;
			}
			--hi;
			i64 h = hs(l - hi, r + hi);
			interval[h] = {l - hi, r + hi};
			++mp[{2 * hi + r - l + 1, h}];
		}
	}

	i64 ans = 0;

	while(!mp.empty()) {
		auto [len, h] = mp.begin()->fi;
		int frq = mp.begin()->sc;
		ans = max(ans, (i64)len * frq);
		mp.erase(mp.begin());
		if(len <= 2) continue;
		auto [l, r] = interval[h];
		i64 nh = hs(l + 1, r - 1);
		mp[{len - 2, nh}] += frq;
		interval[nh] = {l + 1, r - 1};
	}

	return ans;
}

void solve() {
	string s;
	cin >> s;
	cout << f(s) << '\n';
}

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

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