Submission #925512

#	Time	Username	Problem	Language	Result	Execution time	Memory
925512		ayankarimova	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	193 ms	28452 KiB

palindromic

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define ll long long
const ll sz=1e6+5;
const ll p=167;
ll h[sz];
ll pw[sz], mod=1e9+7, n;
bool check(ll a, ll b, ll x)
{

    ll h1=h[a+x-1];
    if(a) h1-=h[a-1];
    h1=(h1+mod)%mod;
    ll h2=h[b+x-1];
    if(b) h2-=h[b-1];
    h2=(h2+mod)%mod;
    return (h1*pw[b-a]%mod==h2);
}
int main(){

    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    pw[0]=1;
    for(int i=1; i<sz; i++){
        pw[i]=pw[i-1]*p%mod;
    }
    ll t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        n=s.length();
        h[0]=s[0]-'a'+1;
        for(int i=1; i<n; i++){
            h[i]=h[i-1]+(s[i]-'a'+1)*pw[i]%mod;
            h[i]%=mod;
        }
        ll l=0, r=n-1, ans=0;
        for(l=0; l<n; ){
            for(int k=1; k<=n; k++){
                if(check(l, r-k+1, k)){
                    ans++;
                    if(r-k+1!=l) ans++;
                    //cout<<l<<' '<<r<<' '<<r-k+1<<' '<<k<<endl;
                    l+=k;
                    r-=k; break;
                }
            }
            if(l>=r){
                ans+=(l==r);
                break;
            }
        }
        cout<<ans<<endl;
    }
}

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