Submission #243284

#	Time	Username	Problem	Language	Result	Execution time	Memory
243284		Lawliet	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	644 ms	17840 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 1000010;

int prime = 31;
int mod = 1000000009;

int n;

lli pot[MAXN];
lli pHash[MAXN];

string s;

int getHash(int L, int R)
{
	lli ans = pHash[R + 1];
	ans -= pHash[L]*pot[R - L + 1];

	ans %= mod;
	if( ans < 0 ) ans += mod;

	return (int)ans;
}

int main()
{
	int t;
	cin >> t;

	pot[0] = 1;

	for(int i = 1 ; i < MAXN ; i++)
		pot[i] = pot[i - 1]*prime, pot[i] %= mod;

	while( t-- )
	{
		cin >> s;
		n = (int)s.size();

		for(int i = 1 ; i <= n ; i++)
		{
			pHash[i] = pHash[i - 1]*prime + s[i - 1] - 'a';
			pHash[i] %= mod;
		}

		int sz = 1, ans = 0;
		int l = 0, r = n - 1;

		while( l <= r )
		{
			sz = 1;

			while( getHash( l , l + sz - 1 ) != getHash( r - sz + 1 , r ) )
				sz++;

			ans++;
			l += sz; r -= sz;

			if( l <= r + 1 ) ans++;
		}

		printf("%d\n",ans);
	}
}

• Subtask 1: 15 / 15
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 40 / 40