제출 #748646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748646		mariowong	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	1934 ms	19032 KiB

palindromic

#include <bits/stdc++.h>
#define hmod (long long)99999989
using namespace std;
 
int t,n,l,r,anss;
long long a[1000005],sum;
string s;
long long fpow(long long a,long long b){
	long long ans=1,base=a;
	while (b > 0){
		if ((b&1) == 1) ans=ans*base%hmod;
		base=base*base%hmod;
		b/=2;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin >> t;
	while (t--){
		cin >> s; n=s.length();
		sum=1;
		for (int i=0;i<n;i++){
			a[i]=(s[i]-'a')*sum;
			a[i]+=a[i-1];
			a[i]%=hmod;
			sum*=26; sum%=hmod;
		}
		l=0; r=n-1; anss=0;
		for (int i=0;i<n;i++){
			if (r-(i-l+1)+1 <= i){
				if (l <= r)
				anss++;
				break;
			}
			if (l == 0 && 
			((a[i]+hmod)%hmod*fpow(fpow(26,hmod-2),l))%hmod == 
			    ((a[r]-a[r-(i-l+1)]+hmod)%hmod*fpow(fpow(26,hmod-2),r-(i-l+1)+1))%hmod
			){
			    anss+=2;
				r=r-(i-l+1);
			    l=i+1;	
			}
			else
			if (l != 0 &&
				((a[i]-a[l-1]+hmod)%hmod*fpow(fpow(26,hmod-2),l))%hmod == 
			    ((a[r]-a[r-(i-l+1)]+hmod)%hmod*fpow(fpow(26,hmod-2),r-(i-l+1)+1))%hmod
				){
			    anss+=2;
				r=r-(i-l+1);
			    l=i+1;	
			}
		}
		cout << anss << "\n";
	}
	return 0;
}

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