제출 #916707

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916707		vjudge1	Palindromic Partitions (CEOI17_palindromic)	C++17	60 / 100	7 ms	1372 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;

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

    int countedch=0;
    int piececounts=0;

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

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

int main()
{
    int n;
    char word[510000];
    cin>>n;
    for(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