Submission #221892

#	Time	Username	Problem	Language	Result	Execution time	Memory
221892		MKopchev	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	223 ms	28592 KiB

palindromic

#include<bits/stdc++.h>
using namespace std;

const int nmax=1e6+42,base=29,mod=1e9+7;

int n;
long long pref[nmax],st[nmax];

long long get_hash(long long s,long long t)
{
    long long ret=pref[t];

    if(s)ret=ret-pref[s-1]*st[t-s+1];

    ret=ret%mod;

    ret=(ret+mod)%mod;

    return ret;
}
int solve()
{
    string s;
    cin>>s;

    n=s.size();

    st[0]=1;
    for(int i=1;i<=n;i++)st[i]=st[i-1]*base%mod;

    for(int i=0;i<n;i++)
    {
        pref[i]=0;
        if(i)pref[i]=pref[i-1]*base;
        pref[i]=pref[i]+s[i]-'a'+1;

        pref[i]=pref[i]%mod;
    }

    int ret=0,l=0,r=n-1;

    while(l<=r)
    {
        for(int i=0;true;i++)
        {
            int l_other=l+i;

            int r_other=r-i;

            if(l_other>=r_other)return ret+1;

            if(get_hash(l,l_other)==get_hash(r_other,r))
            {
                ret=ret+2;
                l=l_other+1;
                r=r_other-1;
                break;
            }
        }
    }

    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    int t;
    cin>>t;
    for(int i=1;i<=t;i++)cout<<solve()<<endl;

    return 0;
}

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