Submission #113914

#	Time	Username	Problem	Language	Result	Execution time	Memory
113914		ckodser	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	301 ms	55092 KiB

palindromic

#include<bits/stdc++.h>

#define ll long long
#define pb push_back
#define mp make_pair
#define ld long double
#define F first
#define S second
#define pii pair<ll,ll> 

using namespace :: std;

const ll mod=1e9+7;
const ll maxn=1e6+500;
const ll inf=1e9+900;
const ll base=373;
ll tav[maxn];


ll h[maxn];
string globs;
void make_hash(string s){
    globs=s;
    ll n=s.size();
    h[0]=s[0];
    for(ll i=1;i<n;i++){
	h[i]=(h[i-1]*base+s[i])%mod;
    }
}
inline ll ok(ll a){
    if(a>=mod)return a-mod;
    return a;
}
ll find_hash(ll l,ll r){
    if(l==0)return h[r];
    return ok(h[r]-(h[l-1]*tav[r-l+1])%mod+mod);
}
bool is_equal(ll l,ll r,ll L,ll R){/*
    bool ans=1;
    for(ll i=0;i<r-l+1;i++){
	if(globs[l+i]!=globs[L+i]){
	    ans=0;
	}
    }
    return ans;*/
    return (find_hash(l,r)==find_hash(L,R));
}

ll dp[maxn];
ll maxT[maxn];
ll minT[maxn];
ll kia[maxn];
ll solve(string s){
    ll n=s.size();
    make_hash(s);
    memset(maxT,0,sizeof maxT);
    memset(dp,0,sizeof dp);
    memset(minT,0,sizeof minT);
    memset(kia,63,sizeof kia);

    for(ll l=(n-1)/2;l>=0;l--){
	ll r=n-l-1;
	if(l==r){
	    maxT[l]=0;
	}
	else{
	    maxT[l]=0;
	    ll res=min(r-l,maxT[l+1]+2);
	    while(res>0 && !is_equal(l,l+res-1,r-res+1,r)){
		res--;
	    }
	    maxT[l]=res;
	}
    }	
    for(ll l=(n-1)/2;l>=0;l--){
	ll r=n-l-1;
	if(l==r){
	    minT[l]=1;//set kia?
	}
	if(maxT[l]*2<=r-l+1){
	    ll last=maxT[l]+l;
	    ll v=kia[last];
	    if(v!=kia[maxn-1]){
		minT[l]=v;
	    }else{
		minT[l]=maxT[l];
		if(minT[l]==0){
		    minT[l]=r-l+1;
		}
	    }
	}else{
	    ll t=maxT[l]*2-(r-l+1);
	    minT[l]=minT[(n-t)/2];
	}
	kia[minT[l]+l]=min(kia[minT[l]+l],minT[l]);
    }
    for(ll l=(n-1)/2;l>=0;l--){
	ll r=n-l-1;
	if(l==r){
	    dp[l]=1;
	}
	else{
	    if(minT[l]==r-l+1){
		dp[l]=1;
	    }else{
		dp[l]=2+dp[l+minT[l]];
	    }
	}
//	cout<<l<<' '<<r<<":"<<minT[l]<<' '<<maxT[l]<<' '<<dp[l]<<endl;

    }
    return dp[0];
}

int main(){
    tav[0]=1;
    for(ll i=1;i<maxn;i++){
	tav[i]=(tav[i-1]*base)%mod;
    }

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll 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