Submission #751567

#	Time	Username	Problem	Language	Result	Execution time	Memory
751567		Fidan	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	157 ms	18132 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=ll(a); i<ll(b); i++)
#define repn(i, a, b) for(ll i=ll(b)-1; i>=ll(a); i--)
#define be begin()
#define en end()
#define ff first
#define ss second
#define si size()
const ll mod=(1e9)+9;
void solve(){
	string s;
	cin>>s;
	ll n=s.si;
	ll l=0, h=n-1;
	ll s1=0, s2=0;
	ll sum=0;
	map<char, ll> mp;
	rep(i, 0, 26){
		mp[97+i]=i;
	}
	vector<ll> pw(n+10, 1);
	rep(i, 1, n+10){
		pw[i]=(pw[i-1]*26)%mod;
	}
	ll x=0;
	while(l<h){
		s1=(s1*26)%mod;
		s1=(s1+s[l])%mod;
		s2=(s2+(pw[x]*s[h])%mod)%mod;
		if(s1==s2){
			x=-1;
			sum+=2;
			s1=0, s2=0;
		}
		x++;
		l++, h--;
	}
	if(s1>0 || s2>0) sum++;
	else if(l==h) sum++;
	cout<<sum<<'\n';
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

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