Submission #1284780

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284780		WH8	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	166 ms	11272 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
const int q=131, m=1e9+7;

signed main(){
	int t;cin>>t;
	auto c=[&](char in)->int{
		int res=in-'a';
		//~ cout<<in<<" "<<res<<endl;
		return res;
	};
	vector<int> pre(1e6, 1);
	for(int i=1;i<1e6;i++){
		pre[i]=(pre[i-1]*q)%m;
	}
	while(t--){
		string s;
		cin>>s;
		int n=s.size(), sm=0, a=0, b=0, p=0;
		for(int i=0;i<n/2;i++){
			//~ printf("before %lld %lld\n", a, b);
			b=(b*q+c(s[n-i-1]))%m;			
			a=(a+c(s[i])*pre[i-p])%m;
			//~ printf("%lld : %lld %lld\n", i, a, b);

			if(a==b){
				bool ok=true;
				int s1=p,s2=n-i-1;
				for(int j=0;j<=i-p;j++){
					if(s[s1+j]!=s[s2+j]){
						ok=false;
						break;
					}
				}
				if(ok){
					p=i+1;
					sm+=2;
					a=0, b=0;
				}
			}
		}
		cout<<sm+(n%2==0 and a==0 and b==0? 0:1)<<'\n';
	}
}

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