Submission #243283

#	Time	Username	Problem	Language	Result	Execution time	Memory
243283		Lawliet	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	832 ms	33328 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 1000010;

int prime[] = { 17 , 31 };
int mod[] = { 1000000007 , 1000000009 };

int n;

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

string s;

int getHash(int L, int R, int p)
{
	L++; R++;

	int sz = R - L + 1;

	lli ans = pHash[R][p];
	ans -= pHash[L - 1][p]*pot[sz][p];

	ans %= mod[p];
	if( ans < 0 ) ans += mod[p];

	return (int)ans;
}

bool areEqual(int L1, int R1, int L2, int R2)
{
	if( getHash( L1 , R1 , 0 ) != getHash( L2 , R2 , 0 ) ) return false;
	if( getHash( L1 , R1 , 1 ) != getHash( L2 , R2 , 1 ) ) return false;
	return true;
}

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

	pot[0][0] = pot[0][1] = 1;

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

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

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

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

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

			while( !areEqual( l , l + sz - 1 , 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