Submission #885183

#	Time	Username	Problem	Language	Result	Execution time	Memory
885183		12345678	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	85 ms	26916 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int nx=1e6+5, mod=1e9+7;
ll n, t, p[nx], st, ed, vl, qs[nx], sz, cnt;
string s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    p[0]=1;
    for (int i=1; i<nx; i++) p[i]=(p[i-1]*26)%mod;
    cin>>t;
    while (t--)
    {
        cin>>s;
        cnt=st=0;
        n=s.size();
        qs[0]=s[0]-'a';
        for (int i=1; i<n; i++) qs[i]=(qs[i-1]+(s[i]-'a')*p[i])%mod;
        while (st<=(n-1)/2)
        {
            vl=0;
            bool can=0;
            for (int i=st; i<=(n/2); i++)
            {
                vl=(vl+(s[i]-'a')*p[i-st])%mod;
                ed=n-1-st;
                sz=i-st+1;
                if (st+sz-1>=ed-sz+1) break;
                //cout<<st<<' '<<sz<<' '<<ed<<' '<<qs[ed]-qs[ed-sz]<<' '<<vl<<' '<<vl*p[ed-sz+1]<<'\n';
                if (((qs[ed]-qs[ed-sz])%mod+mod)%mod==(vl*p[ed-sz+1])%mod)
                {
                    cnt+=2;
                    st=i+1;
                    can=1;
                    break;
                }
            }
            if (!can) {cnt++; break;}
        }
        cout<<cnt<<'\n';
    }
}

/*
10
cars
cac
cactuscac
bob
bbobb
bacocab
bababababababa
bacbacbacbacbacbacbacbacbacbacbac
sasa
sddsa

1
sasa
*/

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