Submission #397431

#	Time	Username	Problem	Language	Result	Execution time	Memory
397431		Nicholas_Patrick	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	440 ms	37344 KiB

palindromic

#include <iostream>
#include <queue>
#include <array>
#include <string>
using namespace std;

const int hus=3;
const int mod[]={0x3fffffdd, 0x3fffffd7, 0x3fffffad};
const int base=123;
using hash_t=array<int, hus>;
hash_t powers[1000001];
void getPowers(){
	for(int i=hus; i--;)
		powers[0][i]=1;
	for(int i=0; i<1000000; i++){
		for(int j=hus; j--;)
			powers[i+1][j]=(long long)powers[i][j]*base%mod[j];
	}
}
vector<hash_t> getHash(string& s){
	int n=s.size();
	vector<hash_t> ret(n+1);
	for(int i=hus; i--;)
		ret[0][i]=0;
	for(int i=0; i<n; i++){
		for(int j=hus; j--;)
			ret[i+1][j]=(ret[i][j]+(long long)powers[i][j]*s[i])%mod[j];
	}
	return ret;
}
bool match(vector<hash_t>& s, int sl, int sr, vector<hash_t>& t, int tl, int tr){
	if(sl<tl){
		for(int i=hus; i--;){
			if(((long long)(s[sr][i]-s[sl][i])*powers[tl-sl][i]-t[tr][i]+t[tl][i])%mod[i])
				return false;
		}
		return true;
	}else if(sl>tl){
		for(int i=hus; i--;){
			if(((long long)(t[tr][i]-t[tl][i])*powers[sl-tl][i]-s[sr][i]+s[sl][i])%mod[i])
				return false;
		}
		return true;
	}else{
		for(int i=hus; i--;){
			if((s[sr][i]-s[sl][i]-t[tr][i]+t[tl][i])%mod[i])
				return false;
		}
		return true;
	}
}
int solve(string& s){
	int n=s.size();
	auto rec=getHash(s);
	int ret=0;
	int l=0, r=n;
	for(int i=1; l<r; i++){
		if(match(rec, l, i, rec, r-(i-l), r)){
			ret+=2;
			r-=i-l;
			l=i;
		}
	}
	if(r<l)
		ret--;
	return ret;
}
int main(){
	getPowers();
	int t;
	cin>>t;
	while(t--){
		string s;
		cin>>s;
		cout<<solve(s)<<endl;
	}
}

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