Submission #987128

#	Time	Username	Problem	Language	Result	Execution time	Memory
987128		irmuun	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	1955 ms	18428 KiB

palindromic

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const ll mod=1e9+9,p=37,N=1e6+5;

ll t,n,pre[N];
string s;

ll binpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1){
            res=res*a%mod;
        }
        a=a*a%mod;
        b=b>>1;
    }
    return res;
}
ll inv(ll a){
    return binpow(a,mod-2);
}

ll f(ll l,ll r){
    return (pre[r]-pre[l-1]+mod)%mod*inv(binpow(p,l))%mod;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--){
        cin>>s;
        n=s.size();
        ll cur=1;
        pre[0]=0;
        for(ll i=0;i<n;i++){
            cur=cur*p%mod;
            pre[i+1]=(pre[i]+cur*(s[i]-'a'+1))%mod;
        }
        ll ans=0,l=1,r=n;
        while(l<=r){
            bool found=false;
            for(ll i=1;i<=(r-l+1)/2;i++){
                if(f(l,l+i-1)==f(r-i+1,r)){
                    l+=i;
                    r-=i;
                    ans+=2;
                    found=true;
                    break;
                }
            }
            if(!found) break;
        }
        if(l<=r){
            ans++;
        }
        cout<<ans<<"\n";
    }
}

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