Submission #1226772

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226772		lukasuliashvili	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	135 ms	10240 KiB

palindromic

#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int mod=1e9+7;
const int N=1e6+4;
const int X=53;

int hshl,hshr,ans,sig,X1[N],srsz,slsz;

string sr,sl,s,cal;
void calc(int x){
    X1[0]=1;
    X1[1]=x;
    rep(i,2,1e6){
        X1[i]=(X1[i-1]*x)%mod;
    }
}
int updatel(int prv,int hsh , char add){
    int X2;
    X2=X1[prv]%mod;//X2=X^prv.size();
    hsh = (hsh+X2*((int)add-'a'+1) %mod)%mod;
    return hsh;
}
int updater(int prv,int hsh,char add){
    hsh = (hsh*X +((int)add-'a'+1))%mod;
    return hsh;
}
signed main(){
    int t;
    cin>>t;
    calc(X);

    while(t--){
        ans=0;
        sig=0;
        cin>>s;
        int l=0;
        int r=s.size()-1;
        //updater marjvnidan emateba 
        //updatel marcxnidan emateba 
        srsz=0;
        slsz=0;
        hshr=0;
        hshl=0;
        while(l<r){
            hshr=updatel(srsz,hshr,s[r]);
            hshl=updater(slsz,hshl,s[l]);
            srsz++;
            slsz++;
            l++;
            r--;
            if(hshr!=hshl){
                continue;
            }
            else{
                ans+=2;
                sig+=srsz*2;
                srsz=0;
                slsz=0;
                hshl=0;
                hshr=0;
            }
        }
        if(sig!=s.size() ){
            ans++;
        }
        cout<<ans<<endl;
        
    }
}

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