Submission #1226750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226750		lukasuliashvili	Palindromic Partitions (CEOI17_palindromic)	C++20	0 / 100	9 ms	8004 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 
        hshl=updater(0,0,s[l]);
        hshr=updatel(0,0,s[r]);
        //cout<<hshl<<" "<<hshr<<endl;
        srsz=1; slsz=1; sl=s[l]; sr=s[r]; r--; l++;
        if(hshr==hshl){
            ans+=2;
            sig+=2;
            hshr=0;
            hshl=0;
            sl="";
            sr="";
            srsz=0;
            slsz=0;
        }
        while(l<r){
            sl+=s[l]; sr=s[r]+sr;
            //cout<<sl<<" "<<sr<<endl;
            //cout<<srsz<<" "<<slsz<<endl;
            hshr=updatel(srsz,hshr,s[r]);
            hshl=updater(slsz,hshl,s[l]);
            srsz++;
            slsz++;
            l++;
            r--;
            if(hshr!=hshl){
                continue;
            }
            else{
                ans+=2;
                sig+=sr.size()*2;
                srsz=0;
                slsz=0;
                sr="";
                sl="";
                hshl=0;
                hshr=0;
            }
        }
        if(sig!=s.size()){
            ans++;
        }
        cout<<ans<<endl;
        
    }
}

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