Submission #721390

#	Time	Username	Problem	Language	Result	Execution time	Memory
721390		n0sk1ll	Palindromes (APIO14_palindrome)	C++14	23 / 100	1068 ms	2140 KiB

palindrome

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (int i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
//const int mod = 1000000007;







//Note to self: Check for overflow

#pragma GCC optimize ("Ofast")

int power(int a, int n, int mod)
{
    li c=1;
    while (n)
    {
        if (n&1) (c*=a)%=mod;
        a=(li)a*a%mod,n>>=1;
    }
    return c;
}

struct hesiranje
{
    int p,mod;
    int w[26];

    void setprost(int _)
    {
        p=_;
    }
    void setmod(int _)
    {
        mod=_;
    }

    int ps[10004],pi[10004];

    int pre[10004],suf[10004];

    void build(string s, int n)
    {
        mt19937 rng(time(NULL));
        ff(i,0,26) w[i]=rng()%mod;

        ps[0]=1,pi[0]=1;
        fff(i,1,n) ps[i]=(li)ps[i-1]*p%mod;
        fff(i,1,n) pi[i]=power(ps[i],mod-2,mod);

        fff(i,1,n) pre[i]=((li)pre[i-1]*p+w[s[i-1]-'a'])%mod;
        bfff(i,1,n) suf[i]=((li)suf[i+1]*p+w[s[i-1]-'a'])%mod;
    }

    int Hash(int l, int r)
    {
        return (pre[r]+mod-(li)pre[l-1]*ps[r-l+1]%mod)%mod;
    }

    int rHash(int l, int r)
    {
        return (suf[l]+mod-(li)suf[r+1]*ps[r-l+1]%mod)%mod;
    }
} h1,h2;

int main()
{
    FAST;

    string s; cin>>s;
    int n=(int)s.size();

    h1.setprost(1000003),h1.setmod(998244353);
    h2.setprost(998244353),h2.setmod(1000000007);
    h1.build(s,n),h2.build(s,n);

    li ans=0;
    fff(k,1,n)
    {
        vector<li> kolko;
        fff(i,k,n) if (h1.Hash(i-k+1,i)==h1.rHash(i-k+1,i) && h2.Hash(i-k+1,i)==h2.rHash(i-k+1,i))
        {
            li sta=(li)h1.Hash(i-k+1,i)*(1ll<<30) + h2.Hash(i-k+1,i);
            kolko.pb(sta);
        }

        if (!kolko.empty())
        {
            int br=1;
            ans=max(ans,(li)k);
            sort(all(kolko));
            ff(i,1,(int)kolko.size())
            {
                if (kolko[i]==kolko[i-1]) br++;
                else
                {
                    ans=max(ans,(li)k*br);
                    br=1;
                }
            }
            ans=max(ans,(li)k*br);
        }
    }
    cout<<ans<<"\n";
}

//Note to self: Check for overflow

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27