Submission #1170864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170864		AlgorithmWarrior	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	222 ms	9032 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

int const BASE=31;
int const MOD=1e9+7;
int const MAX=1e6+5;
int hashes[MAX];
char sir[MAX];
int n;
int basepow[MAX];

void precalc(){
    basepow[0]=1;
    int i;
    for(i=1;i<MAX;++i)
        basepow[i]=1LL*BASE*basepow[i-1]%MOD;
}

void read(){
    cin.getline(sir+1,MAX);
    n=strlen(sir+1);
    int i;
    for(i=1;i<=n;++i)
        hashes[i]=(1LL*BASE*hashes[i-1]%MOD+sir[i]-'a'+1)%MOD;
}

int hashy(int l,int r){
    return (hashes[r]-1LL*hashes[l-1]*basepow[r-l+1]%MOD+MOD)%MOD;
}

int solve(int st,int dr){
    if(st>dr)
        return 0;
    int l=st,r=dr;
    for(;l<r;++l,--r)
        if(hashy(st,l)==hashy(r,dr))
            return 2+solve(l+1,r-1);
    return 1;
}

int main()
{
    precalc();
    int testcases;
    cin>>testcases;
    cin.get();
    while(testcases--){
        read();
        cout<<solve(1,n)<<'\n';
    }
    return 0;
}

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