Submission #37485

#	Time	Username	Problem	Language	Result	Execution time	Memory
37485		MatheusLealV	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	166 ms	42168 KiB

palindromic

#include <bits/stdc++.h>
#define X 145443351LL
#define mod 1000000007LL
using namespace std;
typedef long long ll;

ll Hash[1000010], n, pot[1000010];

inline bool compare(int i, int j, int ii, int jj)
{
	ll dx = (i > 0 ? Hash[i - 1] : 0);

	ll A = (mod + Hash[j] - dx)%mod;

	ll dx2 = (ii > 0 ? Hash[ii - 1] : 0);

	ll A2 = (mod + Hash[jj] - dx2)%mod;

	return (((A*pot[ii])%mod) == ((A2*pot[i])%mod));
}

string s;

int solve(int ini)
{
	int fim = s.size() - 1 - ini;

	if(ini == fim) return 1;

	if(ini > fim) return 0;

	int best = 1;

	for(int p = ini; p <= (ini + fim)/2; p++)
	{
		if(compare(ini, p, fim - p + ini, fim))
		{
			best = max(best, 2 + solve(p + 1));

			break;
		}
	}

	return best;
}

int T;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>T;

	pot[0] = 1;

	for(int i = 1; i < 1000010; i++) pot[i] = (pot[i - 1]*X)%mod;

	while(T--)
	{
		cin>>s;

		n = s.size();

		Hash[0] = 0;

		for(int i = 0; i < n; i++)
		{
			if(i > 0) Hash[i] = Hash[i - 1];

			Hash[i] = (Hash[i] + s[i]*pot[i])%mod;
		}

		cout<<solve(0)<<"\n";
	}
}

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