Submission #1211549

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211549		vukhacminh	Palindromic Partitions (CEOI17_palindromic)	C++20	100 / 100	99 ms	19568 KiB

palindromic

/**
*    Author :  Vu Khac Minh
**/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9+7;
const int base = 31;
ll Hash[maxn],Pow[maxn],n,rHash[maxn];
ll gethash(int l,int r)
{
    return (Hash[r] - Hash[l-1] * Pow[r-l+1]%mod + mod)%mod;
}
int calc(int l,int r)
{
    for(int len = 1;2*len<=r-l+1;len++)
        if(gethash(l,l+len-1) == gethash(r-len+1,r))
            return 2  + calc(l+len,r-len);
    return (l<=r);
}
string s;
void solve()
{
    cin>>s;
    n = s.length();
    s = ' ' + s;
    for(int i =1;i<=n;i++) Hash[i] = (Hash[i-1] *base + s[i] - 'a')%mod;
    cout<<calc(1,n)<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest;
    cin>>ntest;
    Pow[0] = 1;
    for(int i =1;i<maxn;i++) Pow[i] = Pow[i-1] * base%mod;
    while(ntest--) solve();
    return 0;
}

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