Submission #578234

#	Time	Username	Problem	Language	Result	Execution time	Memory
578234		andrei_boaca	Palindromic Partitions (CEOI17_palindromic)	C++14	100 / 100	302 ms	28856 KiB

palindromic

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
string s;
int t,n;
ll baza=31,mod=1e9+7;
ll h[1000005],pw[1000005];
ll gethash(ll st,ll dr)
{
    ll val=(h[dr]-(h[st-1]*pw[dr-st+1])%mod+mod)%mod;
    return val;
}
int getans(int l,int r)
{
    if(l>r)
        return 0;
    for(int last=l;last<=r;last++)
    {
        int lg=last-l+1;
        int poz=r-lg+1;
        if(poz>last)
        {
            ll h1=gethash(l,last);
            ll h2=gethash(poz,r);
            if(h1==h2)
                return 2+getans(last+1,poz-1);
        }
    }
    return 1;
}
void solve()
{
    cin>>s;
    n=s.size();
    s=" "+s;
    pw[0]=1;
    for(int i=1;i<=n;i++)
    {
        h[i]=((h[i-1]*baza)%mod+s[i]-'a'+1)%mod;
        pw[i]=(pw[i-1]*baza)%mod;
    }
    cout<<getans(1,n)<<'\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--)
        solve();
    return 0;
}

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