oj.uz

Submission #13202

# Submission time Handle Problem Language Result Execution time Memory
13202 2015-02-02T15:18:27 Z baneling100 Palindromes (APIO14_palindrome) C++
100 / 100
 857 ms 46496 KB 
#include <stdio.h>
#include <algorithm>
#include <string.h>
#define N_MAX 300000

using namespace std;

pair <int,int> PAL[4*N_MAX];
int N, N_, MA[2*N_MAX], SA[2*N_MAX], LCP[2*N_MAX], STK[2][2*N_MAX], Top, Temp[2*N_MAX];
int Loc[2*N_MAX], Cnt, POS1[4*N_MAX], POS2[4*N_MAX], Rank[4*N_MAX], Sum[2*N_MAX], Order[2*N_MAX];
char S[2*N_MAX+1], S_[N_MAX+2];
long long Ans;

void input(void) {

    int i;

    scanf("%s",&S_[1]);
    N_=strlen(&S_[1]);
    for(i=1 ; i<=N_ ; i++) {
        S[2*i-1]=S_[i];
        S[2*i  ]='z'+1;
    }
    S[2*N_]=NULL;
    N=2*N_-1;
}

void manacher(void) {

    int i, j=0;

    for(i=1 ; i<=N ; i++) {
        i<=j+MA[j] ? MA[i]=min(j+MA[j]-i,MA[2*j-i]) : MA[i]=0;
        while(i+MA[i]+1<=N && S[i-MA[i]-1]==S[i+MA[i]+1]) MA[i]++;
        if(j+MA[j]<i+MA[i])
            j=i;
    }
}

void suffixArray(void) {

    int i, len, M=max(N,27), zero;

    for(i=1 ; i<=N ; i++)
        Rank[i]=S[i]-'a'+1;
    for(len=1 ; len<N ; len<<=1) {
        for(i=0 ; i<=M ; i++) Sum[i]=0;
        zero=0;
        for(i=1 ; i<=N ; i++) Sum[Rank[i+len]]++;
        for(i=1 ; i<=M ; i++) Sum[i]+=Sum[i-1];
        for(i=1 ; i<=N ; i++) {
            if(Rank[i+len])
                Order[++Sum[Rank[i+len]-1]]=i;
            else
                Order[++zero]=i;
        }
        for(i=0 ; i<=M ; i++) Sum[i]=0;
        zero=0;
        for(i=1 ; i<=N ; i++) Sum[Rank[Order[i]]]++;
        for(i=1 ; i<=M ; i++) Sum[i]+=Sum[i-1];
        for(i=1 ; i<=N ; i++) {
            if(Rank[Order[i]])
                SA[++Sum[Rank[Order[i]]-1]]=Order[i];
            else
                SA[++zero]=Order[i];
        }
        for(i=1 ; i<=N ; i++) {
            Temp[SA[i]]=Temp[SA[i-1]];
            if(!(Rank[SA[i]]==Rank[SA[i-1]] && Rank[SA[i]+len]==Rank[SA[i-1]+len]))
                Temp[SA[i]]++;
        }
        for(i=1 ; i<=N ; i++)
            Rank[i]=Temp[i];
    }
}

void longestCommonPrefix(void) {

    int i;

    for(i=1 ; i<=N ; i++)
        Loc[SA[i]]=i;
    for(i=1 ; i<=N ; i++) {
        if(LCP[Loc[i-1]])
            LCP[Loc[i]]=LCP[Loc[i-1]]-1;
        while(S[i+LCP[Loc[i]]]==S[SA[Loc[i]-1]+LCP[Loc[i]]]) LCP[Loc[i]]++;
    }
}

void calculate(void) {

    int i, j=0, p;

    for(i=1 ; i<=N ; i++)
        while(j+1<=i+MA[i]) {
            j++;
            PAL[++Cnt]=make_pair(Loc[2*i-j],2*(j-i)+1);
        }
    sort(PAL+1,PAL+Cnt+1);
    j=1;
    STK[0][Top]=-1;
    for(i=1 ; i<=N ; i++) {
        while(STK[0][Top]>=LCP[i]) Top--;
        STK[0][++Top]=LCP[i];
        STK[1][  Top]=i;
        while(j<=Cnt && PAL[j].first==i) {
            p=lower_bound(STK[0]+1,STK[0]+Top+1,PAL[j].second)-STK[0]-1;
            POS1[j]=STK[1][p];
            j++;
        }
    }
    Top=0;
    j=Cnt;
    for(i=N ; i>=1 ; i--) {
        while(STK[0][Top]>=LCP[i+1]) Top--;
        STK[0][++Top]=LCP[i+1];
        STK[1][  Top]=i;
        while(j>=1 && PAL[j].first==i) {
            p=lower_bound(STK[0]+1,STK[0]+Top+1,PAL[j].second)-STK[0]-1;
            POS2[j]=STK[1][p];
            j--;
        }
    }
    for(i=1 ; i<=Cnt ; i++) {
        if(S[SA[PAL[i].first]]=='z'+1) {
            if(Ans<(long long)(PAL[i].second/2)*(POS2[i]-POS1[i]+1))
                Ans=(long long)(PAL[i].second/2)*(POS2[i]-POS1[i]+1);
        }
        else
            if(Ans<(long long)(PAL[i].second/2+1)*(POS2[i]-POS1[i]+1))
                Ans=(long long)(PAL[i].second/2+1)*(POS2[i]-POS1[i]+1);
    }
}

int main(void) {

    input();
    manacher();
    suffixArray();
    longestCommonPrefix();
    calculate();
    printf("%lld",Ans);

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 46496 KB Output is correct - answer is '7'
2 Correct 0 ms 46496 KB Output is correct - answer is '4'
3 Correct 0 ms 46496 KB Output is correct - answer is '9'
4 Correct 0 ms 46496 KB Output is correct - answer is '1'
5 Correct 3 ms 46496 KB Output is correct - answer is '1'
6 Correct 6 ms 46496 KB Output is correct - answer is '2'
7 Correct 0 ms 46496 KB Output is correct - answer is '3'
8 Correct 0 ms 46496 KB Output is correct - answer is '3'
9 Correct 6 ms 46496 KB Output is correct - answer is '15'
10 Correct 0 ms 46496 KB Output is correct - answer is '24'
11 Correct 3 ms 46496 KB Output is correct - answer is '10'
12 Correct 3 ms 46496 KB Output is correct - answer is '24'
13 Correct 6 ms 46496 KB Output is correct - answer is '25'
14 Correct 3 ms 46496 KB Output is correct - answer is '28'
15 Correct 3 ms 46496 KB Output is correct - answer is '2'
16 Correct 0 ms 46496 KB Output is correct - answer is '1'
17 Correct 3 ms 46496 KB Output is correct - answer is '15'
18 Correct 0 ms 46496 KB Output is correct - answer is '18'
19 Correct 3 ms 46496 KB Output is correct - answer is '1176'
20 Correct 0 ms 46496 KB Output is correct - answer is '1225'
21 Correct 0 ms 46496 KB Output is correct - answer is '136'
22 Correct 3 ms 46496 KB Output is correct - answer is '45'
23 Correct 0 ms 46496 KB Output is correct - answer is '2500'
24 Correct 0 ms 46496 KB Output is correct - answer is '380'
25 Correct 0 ms 46496 KB Output is correct - answer is '2304'
26 Correct 0 ms 46496 KB Output is correct - answer is '110'
27 Correct 6 ms 46496 KB Output is correct - answer is '93'
28 Correct 3 ms 46496 KB Output is correct - answer is '729'
29 Correct 0 ms 46496 KB Output is correct - answer is '132'
30 Correct 0 ms 46496 KB Output is correct - answer is '7'
31 Correct 3 ms 46496 KB Output is correct - answer is '8'
32 Correct 3 ms 46496 KB Output is correct - answer is '64'

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 46496 KB Output is correct - answer is '124251'
2 Correct 0 ms 46496 KB Output is correct - answer is '38226'
3 Correct 0 ms 46496 KB Output is correct - answer is '249500'
4 Correct 3 ms 46496 KB Output is correct - answer is '5778'
5 Correct 0 ms 46496 KB Output is correct - answer is '247506'
6 Correct 0 ms 46496 KB Output is correct - answer is '248004'
7 Correct 0 ms 46496 KB Output is correct - answer is '973'
8 Correct 3 ms 46496 KB Output is correct - answer is '123753'
9 Correct 4 ms 46496 KB Output is correct - answer is '2346'
10 Correct 0 ms 46496 KB Output is correct - answer is '53'
11 Correct 0 ms 46496 KB Output is correct - answer is '52'
12 Correct 0 ms 46496 KB Output is correct - answer is '976'

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 46496 KB Output is correct - answer is '12497500'
2 Correct 7 ms 46496 KB Output is correct - answer is '6481800'
3 Correct 13 ms 46496 KB Output is correct - answer is '25000000'
4 Correct 12 ms 46496 KB Output is correct - answer is '17816841'
5 Correct 11 ms 46496 KB Output is correct - answer is '9945'
6 Correct 7 ms 46496 KB Output is correct - answer is '504100'
7 Correct 17 ms 46496 KB Output is correct - answer is '1512930'
8 Correct 15 ms 46496 KB Output is correct - answer is '413'
9 Correct 11 ms 46496 KB Output is correct - answer is '428'
10 Correct 11 ms 46496 KB Output is correct - answer is '7232'

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 46496 KB Output is correct - answer is '1249925001'
2 Correct 114 ms 46496 KB Output is correct - answer is '396337935'
3 Correct 114 ms 46496 KB Output is correct - answer is '2500050000'
4 Correct 125 ms 46496 KB Output is correct - answer is '1016525689'
5 Correct 184 ms 46496 KB Output is correct - answer is '99645'
6 Correct 170 ms 46496 KB Output is correct - answer is '78569380'
7 Correct 140 ms 46496 KB Output is correct - answer is '82810000'
8 Correct 244 ms 46496 KB Output is correct - answer is '3989'
9 Correct 202 ms 46496 KB Output is correct - answer is '125529616'
10 Correct 175 ms 46496 KB Output is correct - answer is '66664'

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 46496 KB Output is correct - answer is '11250075000'
2 Correct 393 ms 46496 KB Output is correct - answer is '894243195'
3 Correct 401 ms 46496 KB Output is correct - answer is '22499400004'
4 Correct 390 ms 46496 KB Output is correct - answer is '2958163321'
5 Correct 610 ms 46496 KB Output is correct - answer is '298935'
6 Correct 472 ms 46496 KB Output is correct - answer is '1210831209'
7 Correct 486 ms 46496 KB Output is correct - answer is '303195156'
8 Correct 857 ms 46496 KB Output is correct - answer is '11804'
9 Correct 853 ms 46496 KB Output is correct - answer is '11813'
10 Correct 601 ms 46496 KB Output is correct - answer is '262144'
11 Correct 452 ms 46496 KB Output is correct - answer is '3750025000'
12 Correct 837 ms 46496 KB Output is correct - answer is '184796836'