Submission #868698

#	Time	Username	Problem	Language	Result	Execution time	Memory
868698		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	110 ms	28568 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int maxn=1e6+7;
const int base=9973;
const int mod=1e9+7;
int pw[maxn], hsh[maxn];

int get(int l, int r)
{
	return (hsh[r]-hsh[l-1]*pw[r-l+1]+mod*mod)%mod;
}

void solve()
{
	string s; cin >> s;
	int N=s.size();
	s=' '+s;
	for (int i=1; i<=N; i++) hsh[i]=(hsh[i-1]*base+s[i]-'a'+1)%mod;
	int l=1, r=N, ans=0;
	while (l<=r)
	{
		if (l==r)
		{
			ans++;
			break;
		}
		for (int i=l; i<=N/2; i++)
		{
			if (get(l, i)==get(N-i+1, r))
			{
				ans+=2;
				l=i+1;
				r=N-i;
				goto GT;
			}
		}
		ans+=(l<r);
		break;
		GT:;
		if (l==r)
		{
			ans++;
			break;
		}
	}
	cout<<ans<<endl;
}

signed main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	pw[0]=1;
	for (int i=1; i<=maxn; i++) pw[i]=pw[i-1]*base%mod;
	int t; cin >> t;
	while(t--) solve();
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:55:35: warning: iteration 1000006 invokes undefined behavior [-Waggressive-loop-optimizations]
   55 |  for (int i=1; i<=maxn; i++) pw[i]=pw[i-1]*base%mod;
      |                              ~~~~~^~~~~~~~~~~~~~~~~
palindromic.cpp:55:17: note: within this loop
   55 |  for (int i=1; i<=maxn; i++) pw[i]=pw[i-1]*base%mod;
      |                ~^~~~~~

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