Submission #624407

#	Time	Username	Problem	Language	Result	Execution time	Memory
624407		Iwanttobreakfree	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	296 ms	26912 KiB

palindromic

#include <iostream>
#include <vector>
using namespace std;
const int MAX_N=1e6+7,t=70,mod=1e9+7;
vector<long long> pre_hash(MAX_N),pre(MAX_N);
int get_hash(int a,int sz){
    //cout<<a<<' '<<sz<<' '<<pre_hash[a]<<' '<<pre[sz]<<'\n';
    return (((pre_hash[a+sz]-pre_hash[a]*pre[sz])%mod)+mod)%mod;
}
bool ok(int i,int j,int mid){
    //cout<<i<<' '<<j<<' '<<mid<<' '<<get_hash(i,mid)<<' '<<get_hash(j,mid)<<'\n';
    return get_hash(i,mid)==get_hash(j,mid);
}
int main(){
    int test;
    string s;
    cin>>test;
    pre[0]=1;
    for(int i=0;i<MAX_N-1;i++)pre[i+1]=(pre[i]*t)%mod;
    while(test--){
        cin>>s;
        int n=s.size();
        for(int i=0;i<n;i++)pre_hash[i+1]=(pre_hash[i]*t+s[i]-'a'+1)%mod;
        int ans=0,last=-1;
        for(int i=0;i<n/2;i++){
            int sz=i-last;
            if(ok(last+1,n-1-last-sz,sz)){
                ans+=2;
                last=i;
            }
        }
        if(n&1||last!=n/2-1)ans++;
        cout<<ans<<'\n';
    }
}

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