Submission #80523

#	Time	Username	Problem	Language	Result	Execution time	Memory
80523		quoriess	Palindromic Partitions (CEOI17_palindromic)	C++14	0 / 100	2 ms	376 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
#define dbg(x) cout<<#x<<" has a value of: "<<x<<"\n";
#define usize(x) (int)(x.size())
#define plist(x) for(int i=0;i<usize(x);i++)cout<<"eleman "<<i<<" = "<<x[i]<<"\n";
#define foreach(x) for(auto item:x)
#define fill(s,x) for(int i=0;i<x;i++)cin>>s[i];
std::ostream& operator<<(std::ostream& os, pair<int,int> p) {
    os << p.first << ", " << p.second;
    return os;
}
const lli HASH_MOD=1e9+7;
const lli HASH_BASE=37;
lli extended(lli a,lli b,lli* x, lli* y){
	if(a==0){
		*x=0;
		*y=1;
		return b;
	}
	lli x1,y1;
	lli gcdv=extended(b%a,a,&x1,&y1);
	*x=y1-(b/a)*x1;
	*y=x1;
	return gcdv;
}
lli inverse(lli a){
	lli x,y;
	extended(a,HASH_MOD,&x,&y);
	return (x+HASH_MOD)%HASH_MOD;
}
lli fastPow(lli a,lli b){
	if(b==0)return 1;
	lli snc=fastPow(a,b/2)*fastPow(a,b/2);
	snc=(snc+HASH_MOD)%HASH_MOD;
	if(b&1)snc*=a;
	return (snc+HASH_MOD)%HASH_MOD;
}
/*
4 bonobo deleted racecar racecars

 * */
int main(){
	int t;
	cin>>t;
	while(t--){
		string s;
		cin>>s;
		int n=s.size();
		vector<lli> pre(n+1);
		for(int i=0;i<n;i++){
			pre[i+1]=(pre[i]*HASH_BASE+s[i]-'a'+1+HASH_MOD)%HASH_MOD;
		}
		lli cvb=0;
		lli cst=0,cend=n;
		int i=1;
		for(;;){
			if(cst+i>=cend-i+1)break;
			//dbg(i);
			//dbg(cst);
			lli on=((pre[cst+i]-pre[cst]*fastPow(HASH_BASE,i))+HASH_MOD)%HASH_MOD;
			lli son=(((pre[cend]-pre[cend-i]*fastPow(HASH_BASE,i))%HASH_MOD)+HASH_MOD)%HASH_MOD;
			if(on==son){
				cvb+=2;
				cst+=i;
				cend-=i;
				i=1;
			}
			else i++;
		}
		if(cst<cend)cvb++;
		cout<<cvb<<"\n";
	}
	return 0;
}

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