Submission #392638

#	Time	Username	Problem	Language	Result	Execution time	Memory
392638		Berted	Palindromes (APIO14_palindrome)	C++17	100 / 100	913 ms	61196 KiB

palindrome

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#define ll long long
using namespace std;

const int SZ = 2;
const ll MD[2] = {1000000007, 420691273};
const ll P[2] = {41, 31};

int N;
ll inv[SZ][300001];

inline ll exp(ll b, ll e, const ll& m)
{
	ll ret = 1;
	while (e)
	{
		if (e & 1) ret = ret * b % m;
		b = b * b % m; e >>= 1;
	}
	return ret;
}

inline void compInverse()
{
	for (int i = 0; i < SZ; i++) {inv[i][0] = 1; inv[i][1] = exp(P[i], MD[i] - 2, MD[i]); }

	for (int i = 2; i <= N; i++)
		for (int j = 0; j < SZ; j++) inv[j][i] = inv[j][i - 1] * inv[j][1] % MD[j];
}

struct RHash
{
	vector<ll> pref[SZ];
	ll K[SZ];
	
	void build(const string &s)
	{
		for (int j = 0; j < SZ; j++) 
		{
			pref[j].assign(s.size() + 1, 0);
			K[j] = 1;
		}
		
		for (int i = 1; i <= s.size(); i++)
		{
			for (int j = 0; j < SZ; j++)
			{
				pref[j][i] = (pref[j][i - 1] + K[j] * (s[i - 1] - 'a' + 1) % MD[j]) % MD[j];
				K[j] = K[j] * P[j] % MD[j];
			}
		}
	}

	inline array<ll, SZ> getHash(int L, int R)
	{
		array<ll, SZ> ret;
		for (int i = 0; i < SZ; i++)
		{
			ret[i] = pref[i][R] - pref[i][L - 1];
			if (ret[i] < 0) ret[i] += MD[i];
			ret[i] = (ret[i] * inv[i][L - 1]) % MD[i];
		}
		return ret;
	}
};

string S, T;
RHash A, B;

ll res = 0;
int ptr = 1, cnt[350001], sz[350001];
map<array<ll, SZ>, int> mp;
vector<int> adj[350001]; 

void DFS(int u)
{
	for (const auto &v : adj[u])
	{
		DFS(v); cnt[u] += cnt[v];
	}
	//cerr << "DFS:" << u << " " << sz[u] << " " << cnt[u] << "\n";
	res = max(res, (ll)cnt[u] * sz[u]);
}

int main()
{
	//freopen("A.in", "r", stdin);
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> S; N = S.size();

	compInverse();
	T = S; reverse(T.begin(), T.end());

	A.build(S); B.build(T);
	for (int i = 0; i < N; i++)
	{
		int L = 1, R = min(i, N - 1 - i) + 1;
		while (L < R)
		{
			int M = L + R >> 1;
			if (A.getHash(i + 1, i + M + 1) == B.getHash(N - i, N - i + M)) {L = M + 1;}
			else {R = M;}
		}
		//cerr << "Solving palindrome: " << i - L + 1 << " " << i << " " << i + L - 1 << "\n";
		array<ll, SZ> cur; int pv = -1;
		for (int j = i + L; j > i; j--)
		{
			cur = A.getHash(i + 1, j);
			if (mp.count(cur))
			{
				if (pv == -1) cnt[mp[cur]]++;
				else adj[mp[cur]].push_back(pv);
				pv = -1; break;	
			}
			else
			{
				//cerr << ptr << " represents " << i << " " << j - 1 << "\n";
				//cerr << cur[0] << " " << cur[1] << "\n";
				sz[ptr] = 2 * (j - i) - 1; mp[cur] = ptr++;
				if (pv == -1) cnt[mp[cur]]++;
				else adj[mp[cur]].push_back(pv);
				pv = mp[cur];
			}
		}
		if (pv != -1) adj[0].push_back(pv);
	}

	DFS(0);
	
	for (int i = 0; i < ptr; i++) {adj[i].clear(); cnt[i] = 0; sz[i] = 0;}
	mp.clear(); ptr = 1;

	for (int i = 1; i < N; i++)
	{
		int L = 1, R = min(i, N - i) + 1;
		while (L < R)
		{
			int M = L + R >> 1;
			if (A.getHash(i + 1, i + M) == B.getHash(N - i + 1, N - i + M)) {L = M + 1;}
			else {R = M;}
		}
		L--;
		//cerr << "Solving palindrome2: " << i - L << " " << i - 1 << " " << i << " " << i + L - 1 << "\n";
		if (L)
		{
			array<ll, SZ> cur; int pv = -1;
			for (int j = i + L; j > i; j--)
			{
				cur = A.getHash(i + 1, j);
				if (mp.count(cur))
				{
					if (pv == -1) cnt[mp[cur]]++;
					else adj[mp[cur]].push_back(pv);
					pv = -1; break;	
				}
				else
				{
					sz[ptr] = 2 * (j - i); mp[cur] = ptr++;
					if (pv == -1) cnt[mp[cur]]++;
					else adj[mp[cur]].push_back(pv);
					pv = mp[cur];
				}
			}
			if (pv != -1) adj[0].push_back(pv);
		}
	}

	DFS(0);

	cout << res << "\n";
	return 0;
}

Compilation message (stderr)

palindrome.cpp: In member function 'void RHash::build(const string&)':
palindrome.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |   for (int i = 1; i <= s.size(); i++)
      |                   ~~^~~~~~~~~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:103:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  103 |    int M = L + R >> 1;
      |            ~~^~~
palindrome.cpp:141:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  141 |    int M = L + R >> 1;
      |            ~~^~~

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