Submission #47178

#	Time	Username	Problem	Language	Result	Execution time	Memory
47178		dongwon0427	Palindromes (APIO14_palindrome)	C++11	58 / 100	1034 ms	38076 KiB

palindrome

/*
god taekyu
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define MAX 300005
int n;
char A[MAX];

int SA[MAX], lcp[MAX];
int ord[MAX],x[MAX],cnt[MAX];
void init() {
    int m = 256;
    for(int i=0;i<n;i++) ord[i] = A[i];
    for(int i=0;i<n;i++) cnt[ord[i]]++;
    for(int i=1;i<=m;i++) cnt[i] += cnt[i-1];
    for(int i=n-1;i>=0;i--) SA[--cnt[ord[i]]] = i;
    for(int j=1;;j<<=1) {
        int p = 0;
        for(int i=n-j;i<n;i++) x[p++] = i;
        for(int i=0;i<n;i++) if(SA[i]>=j) x[p++] = SA[i]-j;
        for(int i=0;i<=m;i++) cnt[i] = 0;
        for(int i=0;i<n;i++) cnt[ord[i]]++;
        for(int i=1;i<=m;i++) cnt[i] += cnt[i-1];
        for(int i=n-1;i>=0;i--) SA[--cnt[ord[x[i]]]] = x[i];
        x[SA[0]] = 0;
        for(int i=1;i<n;i++) {
            x[SA[i]] = x[SA[i-1]];
            if(ord[SA[i]] == ord[SA[i-1]]) {
                if(SA[i]+j < n && SA[i-1]+j < n) {
                    if(ord[SA[i]+j] == ord[SA[i-1]+j]) continue;
                }
            }
            x[SA[i]]++;
        }
        for(int i=0;i<n;i++) ord[i] = x[i];
        m = ord[SA[n-1]];
        if(m == n-1) break;
    }
    int p = 0;
    for(int i=0;i<n;i++) {
        int j = ord[i];
        if(j == 0) {
            if(p != 0) p--;
            continue;
        }
        while(SA[j]+p<n && SA[j-1]+p<n && A[SA[j]+p] == A[SA[j-1]+p]) p++;
        lcp[j] = p;
        if(p!=0) p--;
    }

    //for(int i=0;i<n;i++) {
    //    for(int j=SA[i];j<n;j++) cout<<A[j];
    //    cout<<' '<<lcp[i]<<'\n';
    //}
}
char B[MAX*2];
int dp[MAX*2];
vector<pii> P;
void palin() {
    for(int i=0;i<n;i++) {
        B[2*i] = A[i];
        B[2*i+1] = '*';
    }
    int len = 2*n-1;
    //for(int i=0;i<len;i++) {
    //    cout<<B[i];
    //}
    //cout<<'\n';

    dp[0] = 0;
    int p=0, r=0;
    //cout<<B[0]<<'\n';
    P.push_back(pii(0,1));
    for(int i=1;i<len;i++) {
        if(i<r-1) dp[i] = dp[2*p-i];
        else dp[i] = 0;
        while(i+dp[i]+1<len && i-dp[i]-1>=0 && B[i+dp[i]+1] == B[i-dp[i]-1]) {
            dp[i]++;
            if(r < i+dp[i]) {
                r = i+dp[i];
                p = i;
                //for(int j=i-dp[i];j<=dp[i]+i;j++) if(j%2==0) cout<<B[j];
                int st = (i-dp[i]+1)/2;
                int rad;
                if((i+dp[i])%2 == 0) rad = dp[i]+1;
                else rad =  dp[i];
                P.push_back(pii(st,rad));
                //cout<<'\n';
            }
        }
    }
}
int SP[MAX][20];
void spar() {
    for(int i=0;i<n;i++) SP[i][0] = lcp[i];
    int len = 1;
    for(int j=1;j<20;j++) {
        len*=2;
        for(int i=0;i<n-len+1;i++) {
            SP[i][j] = min(SP[i][j-1], SP[i+len/2][j-1]);
        }
    }

}
int query(int s,int e) {
    int len = e-s+1;
    int j = 1;
    int cnt = 0;
    while(j<=len) j*=2,cnt++;
    j/=2; cnt--;
    return min(SP[s][cnt] , SP[e-j+1][cnt]);
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>A;
    n = strlen(A);

    init();
    palin();


    spar();

    ll ret = 0;
    for(pii x : P) {
        int st = ord[x.first]+1, ed = n-1;
        int ans = st-1;
        while(st<=ed) {
            int mid = (st+ed)/2;
            if(query(ord[x.first]+1 , mid) >= x.second) {
                ans = max(ans , mid);
                st = mid+1;
            } else ed = mid-1;
        }

        int ans2 = ord[x.first]+1;
        st = 1, ed = ord[x.first];
        while(st<=ed) {
            int mid = (st+ed)/2;
            if(query(mid , ord[x.first]) >= x.second) {
                ans2 = min(ans2 , mid);
                ed = mid-1;
            } else st = mid+1;
        }
        //for(int i=x.first;i<x.first+x.second;i++) cout<<A[i];
        //cout<<' '<<(ll)(ans - ans2 + 2) * (ll)x.second<<'\n';
        ret = max(ret , (ll)(ans - ans2 + 2) * (ll)x.second);
    }
    cout<<ret;
    return 0;
}

/*
god taekyu
*/

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