Submission #46275

#	Time	Username	Problem	Language	Result	Execution time	Memory
46275		Pajaraja	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	468 ms	29304 KiB

palindromic

#include <bits/stdc++.h>
#define MOD 1000000009LL
using namespace std;
long long parc[1000007],step[10000007];
int main() 
{
    step[0]=1;
    for(int i=1;i<=1000001;i++) step[i]=(step[i-1]*30)%MOD;
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int n=s.size();
        parc[n]=0;
        for(int i=n-1;i>=0;i--) parc[i]=(30*parc[i+1]+(s[i]-'a'+1))%MOD;
        long long st=1,hsh=0;
        int prev=-1,cnt=1;
        for(int i=0;i<n/2;i++)
        {
            hsh=(hsh+st*(s[i]-'a'+1))%MOD;
            st=(st*30)%MOD;
            if((parc[n-1-i]+MOD-((step[i-prev]*parc[n-1-prev])%MOD))%MOD==hsh)
            {
                st=1;
                hsh=0;
                cnt+=2;
                prev=i;
            }
        }
        if(prev==(n/2-1) && n%2==0) cnt--;
        printf("%d\n",cnt);
    }
}

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