Submission #46160

#	Time	Username	Problem	Language	Result	Execution time	Memory
46160		Extazy	Palindromes (APIO14_palindrome)	C++17	73 / 100	687 ms	62412 KiB

palindrome

#include <bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
const unsigned long long B1 = 131, B2 = 137, MOD = (1e9) + 7;
const int N = 300007;
 
struct rolling_hash {
    unsigned long long h1;
    unsigned h2;
    
    rolling_hash(): h1(0), h2(0) {}
 
    void append(char a) {
        h1*=B1;
        h1+=a-'a'+1;
        h2=(h2*1llu*B2+a-'a'+1)%MOD;
    }
 
    bool operator ==(const rolling_hash &a) const {
        return h1==a.h1 && h2==a.h2;
    }
 
    bool operator <(const rolling_hash &a) const {
        return h1==a.h1 ? h2<a.h2 : h1<a.h1;
    }
};
 
struct hash_rolling_hash {
    unsigned long long operator () (const rolling_hash &a) const {
        return a.h1^(a.h2<<30);
    }
};
 
struct item {
    rolling_hash hash;
    int from,to;
 
    item(){}
    item(rolling_hash a, int b, int c): hash(a), from(b), to(c) {}
    
    bool operator <(const item &a) const {
        return to-from+1==a.to-a.from+1 ? hash<a.hash : to-from+1<a.to-a.from+1;
    }
};
 
int n;
char a[N];
unsigned long long pw1[N];
unsigned pw2[N];
rolling_hash ph[N],sh[N];
unordered_map < rolling_hash, pair < int, int >, hash_rolling_hash > interval;
unordered_map < rolling_hash, int, hash_rolling_hash > current_cnt;
priority_queue < item > q;
long long ans;
list < item > wait[N];
 
inline rolling_hash get_prefix_hash(rolling_hash *a, int l, int r) {
    rolling_hash hl=a[l-1],hr=a[r];
 
    hl.h1*=pw1[r-l+1];
    hl.h2=hl.h2*1llu*pw2[r-l+1]%MOD;
 
    hr.h1-=hl.h1;
    hr.h2-=hl.h2;
    hr.h2+=MOD;
    hr.h2%=MOD;
    
    return hr;
}
 
inline rolling_hash get_suffix_hash(rolling_hash *a, int l, int r) {
    rolling_hash hl=a[l],hr=a[r+1];
    
    hr.h1*=pw1[r-l+1];
    hr.h2=hr.h2*1llu*pw2[r-l+1]%MOD;
 
    hl.h1-=hr.h1;
    hl.h2-=hr.h2;
    hl.h2+=MOD;
    hl.h2%=MOD;
 
    return hl;
}
 
inline bool is_palindrome(int l, int r) {
    return get_prefix_hash(ph,l,r)==get_suffix_hash(sh,l,r);
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i,j;
    rolling_hash h;
 
    pw1[0]=pw2[0]=1;
    for(i=1;i<N;i++) {
        pw1[i]=pw1[i-1]*B1;
        pw2[i]=pw2[i-1]*1llu*B2%MOD;
    }
 
    while((a[++n]=getchar_unlocked())!='\n');
    --n;
 
    h=rolling_hash();
    for(i=1;i<=n;i++) {
        h.append(a[i]);
        ph[i]=h;
    }
 
    h=rolling_hash();
    for(i=n;i>=1;i--) {
        h.append(a[i]);
        sh[i]=h;
    }
 
    for(i=1;i<=n;i++) {
        int left=0,right=min(i,n-i+1),middle;
 
        while(right-left>1) {
            middle=(left+right)/2;
            
            if(is_palindrome(i-middle,i+middle)) left=middle;
            else right=middle;
        }
 
        for(j=left;j>=0;j--) {
            h=get_prefix_hash(ph,i-j,i+j);
 
            if(interval.find(h)!=interval.end()) break;
            
            wait[2*j+1].push_back(item(h,i-j,i+j));
            interval[h]=make_pair(i-j,i+j);
        }
 
        h=get_prefix_hash(ph,i-left,i+left);
        ++current_cnt[h];
    }
 
    for(i=1;i<n;i++) if(a[i]==a[i+1]) {
        int left=0,right=min(i,n-i),middle;
        
        while(right-left>1) {
            middle=(left+right)/2;
 
            if(is_palindrome(i-middle,i+1+middle)) left=middle;
            else right=middle;
        }
 
        for(j=left;j>=0;j--) {
            h=get_prefix_hash(ph,i-j,i+1+j);
 
            if(interval.find(h)!=interval.end()) break;
            
            wait[2*j+2].push_back(item(h,i-j,i+1+j));
            interval[h]=make_pair(i-j,i+1+j);
        }
 
        h=get_prefix_hash(ph,i-left,i+1+left);
        ++current_cnt[h];
    }
 
    int T = n<=100000 ? 2 : 100000;

    for(i=n;i>T;i--) {
        for(item curr: wait[i]) {
            int cnt=current_cnt[curr.hash];
            long long curr_ans=cnt*1ll*i;
            current_cnt.erase(curr.hash);
 
            if(curr_ans>ans) {
                ans=curr_ans;
            }
 
            curr.hash=get_prefix_hash(ph,curr.from+1,curr.to-1);
            pair < int, int > seg=interval[curr.hash];
            curr.from=seg.first;
            curr.to=seg.second;
            current_cnt[curr.hash]+=cnt;
        }
    }
 
    if(n<=100000) for(;i>=1;i--) {
        for(item curr: wait[i]) { 
            int cnt=current_cnt[curr.hash];
            long long curr_ans=cnt*1ll*i;
 
            if(curr_ans>ans) {
                ans=curr_ans;
            }
        }
    }
 
    printf("%lld\n", ans);
    
    return 0;
}

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