Submission #1189384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189384		PieArmy	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	225 ms	46316 KiB

palindromic

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
typedef __int128_t huge;
const huge MOD=(1ll<<61)-1;
const huge K=29;

int n;
int arr[1000023];
int opt[1000023];
int dp[1000023];
huge has[1000023];
huge kat[1000023];

huge cal(int l,int r){
	return (has[r]+MOD-((has[l-1]*kat[r-l+1])%MOD))%MOD;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	int t;cin>>t;
	kat[0]=1;
	for(int i=1;i<=1e6;i++){
		kat[i]=((kat[i-1])*K)%MOD;
	}
	while(t--){
		string s;cin>>s;
		n=s.size();
		for(int i=1;i<=n;i++){
			arr[i]=s[i-1]-'a'+1;
			opt[i]=1;
			dp[i]=0;
			has[i]=has[i-1]*K;
			has[i]+=arr[i];
			has[i]%=MOD;
		}
		dp[n+1]=0;
		opt[n+1]=1;
		int ans=0;
		int las=0;
		for(int i=1;i<=n/2;i++){
			if(cal(opt[i],i)==cal(n-i+1,n-opt[i]+1)){
				opt[i+1]=i+1;
				ans++;
				las=i;
			}
			else opt[i+1]=opt[i];
		}
		cout<<ans*2+(las*2!=n)<<endl;
	}
}

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