Submission #1018193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018193		jk410	Palindromes (APIO14_palindrome)	C++17	73 / 100	449 ms	94644 KiB

palindrome

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#define all(v) v.begin(),v.end()
#define compress(v) v.erase(unique(all(v)),v.end())
#define lbx(v,x) lower_bound(all(v),x)-v.begin()
#define ubx(v,x) upper_bound(all(v),x)-v.begin()
#define maxx(a,b) a=max(a,b)
#define minn(a,b) a=min(a,b)
#define for0(i,n) for (int i=0; i<n; i++)
#define for1(i,n) for (int i=1; i<=n; i++)
#define forr(i,l,r) for (int i=l; i<=r; i++)
#define sz(v) (int)v.size()
using namespace std;
typedef long long ll;
const ll B1=1777;
const ll B2=7499;
const ll B3=6247;
const ll P1=123456791;
const ll P2=1104110479;
const ll P3=998244353;
const int MAX=601557;
ll PowB1[MAX+1],PowB2[MAX+1],PowB3[MAX+1],IPowB1[MAX+1],IPowB2[MAX+1],IPowB3[MAX+1];
ll myPow(ll a,ll b,ll mod){
    ll ret=1;
    while (b){
        if (b&1)
            ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
int N;
string S,A;
int P[MAX*2];
ll H1[MAX],H2[MAX],H3[MAX];
map<array<ll,3>,int> Map;
int CntHash;
vector<int> Adj[MAX+1];
int L[MAX+1];
int Cnt[MAX+1];
bool Visited[MAX+1];
array<ll,3> getHash(int l,int r){
    return {(H1[r]-(l?H1[l-1]:0)+P1)%P1*IPowB1[l]%P1,(H2[r]-(l?H2[l-1]:0)+P2)%P2*IPowB2[l]%P2,(H3[r]-(l?H3[l-1]:0)+P3)%P3*IPowB3[l]%P3};
}
int getIdx(array<ll,3> h,int l,int r){
    if (Map.find(h)!=Map.end())
        return Map[h];
    Map[h]=++CntHash;
    L[CntHash]=r-l+1;
    return CntHash;
}
void solve(int l,int r){
    if (l>r)
        return;
    array<ll,3> h=getHash(l,r);
    int ih=getIdx(h,l,r);
    Cnt[ih]++;
    if (ih!=CntHash)
        return;
    while (l+1<=r-1){
        array<ll,3> nxt=getHash(l+1,r-1);
        int inxt=getIdx(nxt,l+1,r-1);
        bool flag=(inxt!=CntHash);
        Adj[inxt].push_back(ih);
        if (flag)
            break;
        h=nxt;
        ih=inxt;
        l++;
        r--;
    }
}
int dfs(int v){
    if (Visited[v])
        return Cnt[v];
    Visited[v]=true;
    for (int i:Adj[v])
        Cnt[v]+=dfs(i);
    return Cnt[v];
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    PowB1[0]=PowB2[0]=PowB3[0]=1;
    for1(i,MAX){
        PowB1[i]=PowB1[i-1]*B1%P1;
        PowB2[i]=PowB2[i-1]*B2%P2;
        PowB3[i]=PowB3[i-1]*B3%P3;
    }
    IPowB1[MAX]=myPow(PowB1[MAX],P1-2,P1);
    IPowB2[MAX]=myPow(PowB2[MAX],P2-2,P2);
    IPowB3[MAX]=myPow(PowB3[MAX],P3-2,P3);
    for (int i=MAX; i; i--){
        IPowB1[i-1]=IPowB1[i]*B1%P1;
        IPowB2[i-1]=IPowB2[i]*B2%P2;
        IPowB3[i-1]=IPowB3[i]*B3%P3;
    }
    cin>>S;
    N=sz(S);
    for0(i,N){
        H1[i]=((i?H1[i-1]:0)+S[i]*PowB1[i]%P1)%P1;
        H2[i]=((i?H2[i-1]:0)+S[i]*PowB2[i]%P2)%P2;
        H3[i]=((i?H3[i-1]:0)+S[i]*PowB3[i]%P3)%P3;
    }
    A.push_back(S[0]);
    for1(i,N-1){
        A.push_back('.');
        A.push_back(S[i]);
    }
    for (int i=0,r=-1,k=-1; i<N*2-1; i++){
        if (i<=r)
            P[i]=min(P[2*k-i],r-i);
        while (i-P[i]-1>=0&&i+P[i]+1<N*2-1&&A[i-P[i]-1]==A[i+P[i]+1])
            P[i]++;
        if (r<i+P[i]){
            r=i+P[i];
            k=i;
        }
        if (i&1){
            int len=(P[i]+1)/2;
            solve(i/2-len+1,i/2+len);
        }
        else{
            int len=P[i]/2;
            solve(i/2-len,i/2+len);
        }
    }
    assert(CntHash<=N);
    ll ans=0;
    for1(i,CntHash)
        maxx(ans,(ll)L[i]*dfs(i));
    cout<<ans;
    return 0;
}

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