Submission #752807

#	Time	Username	Problem	Language	Result	Execution time	Memory
752807		Username4132	Palindromes (APIO14_palindrome)	C++14	100 / 100	790 ms	59140 KiB

palindrome

#include<iostream>
#include<map>
#include<cassert>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define F first
#define S second

struct hsh{
    int a, b;
    hsh(int A=0, int B=0) : a(A), b(B) {}
};

bool operator<(hsh x, hsh y){
    return x.a==y.a? x.b<y.b : x.a<y.a;
}

const int MOD1=1000000007, MOD2=1000000009, MAXN=600010;
const hsh base = hsh(124523, 3465354);
int n;
ll ans;
map<hsh, int> id;

hsh operator+(hsh x, hsh y){
    int a=(x.a+y.a)%MOD1, b=(x.b+y.b)%MOD2;
    return hsh(a, b);
}

hsh operator-(hsh x, hsh y){
    int a=(x.a-y.a+MOD1)%MOD1, b=(x.b-y.b+MOD2)%MOD2;
    return hsh(a, b);
}

hsh operator*(hsh x, hsh y){
    int a=(((ll)x.a)*y.a)%MOD1, b=(((ll)x.b)*y.b)%MOD2;
    return hsh(a, b);
}

string aux, str;
hsh arr[MAXN], pot[MAXN];
int l=1, r=1, cur, len[MAXN], val[MAXN], par[MAXN], cnt[MAXN];

hsh calc(int le, int ri){
    return arr[ri]-(arr[le]*pot[ri-le]);
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> aux;
    str.resize(2*aux.size() + 1);
    forn(i, aux.size()) str[2*i+1]=aux[i];
    forn(i, aux.size()-1) str[2*i+2]='{';
    str.front()='$', str.back()='^';
    n = str.size();
    pot[0]=hsh(1, 1);
    forn(i, n) arr[i+1]=arr[i]*base+hsh(str[i]-'a'+1, str[i]-'a'+1);
    forn(i, n) pot[i+1]=pot[i]*base;
    forsn(i, 1, n-1){
        int pr=-1;
        if(i<r){
            len[i]=min(r-i, len[l+r-i]);
            pr=id[calc(i-len[i]+1, i+len[i])];
        }
        while(str[i+len[i]]==str[i-len[i]]){
            char ch=str[i+len[i]];
            ++len[i];
            hsh nw=calc(i-len[i]+1, i+len[i]);
            auto itr=id.find(nw);
            if(itr==id.end()){
                id[nw]=cur;
                par[cur]=pr;
                if(ch!='{') val[cur]=len[i];
                pr=cur++;
            }
            else pr=itr->S;
        }
        if(r<i+len[i]) r=i+len[i], l=i-len[i];
        cnt[pr]++;
    }
    dforn(i, cur){
        if(par[i]!=-1) cnt[par[i]]+=cnt[i];
        ans=max(ans, ((ll)val[i])*cnt[i]);
    }
    cout << ans << '\n';
}

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