Submission #917786

#	Time	Username	Problem	Language	Result	Execution time	Memory
917786		HaciyevAlik	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	102 ms	17396 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7,P=47,mx=1e6+5;
ll h[mx],p[mx];
string s;
bool check(ll a,ll b,ll l) {
	if(a>b) return false;
	ll h1=(h[a+l-1]-h[a-1]+mod)%mod;
	ll h2=(h[b+l-1]-h[b-1]+mod)%mod;
	return h1*p[b-a]%mod == h2;
}
void solve() {
	cin >> s;
	ll n=ll(s.size());
	for(ll i=1;i<=n;++i) {
		h[i]=(h[i-1]+(s[i-1]-'a'+1)*p[i-1])%mod;
		h[i]%=mod;
	}
	ll l=1,r=n,res=0;
	while(l<=r) {	
		ll k=1;
		while(!check(l,r-k+1,k)) {
			++k;
		}
		if(l==r-k+1) {
			++res;
			break;
		}
		l+=k,r-=k;
		res+=2;
	}
	cout << res;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	p[0]=1;
	for(ll i=1;i<mx;++i) {
		p[i]=(p[i-1]*P)%mod;
	}
	ll t; cin >> t;
	while(t--) {
		solve();
		cout << '\n';
	}
	return 0;
}

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