Submission #46982

#	Time	Username	Problem	Language	Result	Execution time	Memory
46982		dqhungdl	Palindromic Partitions (CEOI17_palindromic)	C++17	100 / 100	149 ms	42804 KiB

palindromic

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

const int64_t base=26,mod=1e9;
int64_t T,n,M[1000005],H[1000005];
char s[1000005];

int64_t GetHash(int64_t l,int64_t r)
{
    return (H[r]-H[l-1]*M[r-l+1]+mod*mod)%mod;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    M[0]=1;
    for(int64_t i=1;i<=1e6;i++)
        M[i]=M[i-1]*base%mod;
    cin>>T;
    while(T--)
    {
        cin>>s+1;
        n=strlen(s+1);
        for(int64_t i=1;i<=n;i++)
            H[i]=(H[i-1]*base+s[i])%mod;
        int64_t l=1,r=n,res=0;
        while(l<=r)
        {
            int64_t len=1;
            while(l+len-1<r-len+1&&GetHash(l,l+len-1)!=GetHash(r-len+1,r))
                len++;
            if(l+len-1>=r-len+1)
            {
                res++;
                break;
            }
            res+=2;
            l+=len;
            r-=len;
        }
        cout<<res<<"\n";
    }
}

Compilation message (stderr)

palindromic.cpp: In function 'int main()':
palindromic.cpp:23:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin>>s+1;
              ~^~

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