Submission #916710

#	Time	Username	Problem	Language	Result	Execution time	Memory
916710		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	9 ms	1368 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

unsigned int longpal_partitions(char *word)
{
    const unsigned int n=strlen(word);
    const unsigned int prime=131;

    unsigned int countedch=0;
    unsigned int piececounts=0;

    while(countedch*2<n)
    {
        unsigned int lhash=0,rhash=0,power=1;

        for(unsigned int piecesize=1;true;piecesize++)
        {
            unsigned int l=countedch,r=n-countedch-piecesize;
            if(l+piecesize-1>=r)
                return piececounts+1;
            if(piecesize==1)
                power=1;
            else
                power*=prime;
            lhash+=static_cast<unsigned int>(word[l+piecesize-1])*power;
            rhash=static_cast<unsigned int>(word[r])+rhash*prime;
            if(lhash==rhash && strncmp(word+l,word+r,piecesize)==0)
            {
                piececounts+=2;
                countedch+=piecesize;
                break;
            }
        }
    }
    return piececounts;
}

int main()
{
    unsigned int n;
    char word[510000];
    cin>>n;
    for(unsigned int i=0;i<n;i++)
    {
        cin>>word;
        assert(strlen(word)<=510000);
        cout<<longpal_partitions(word)<<endl;
    }
    return 0;
}

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