oj.uz

Submission #9855

# Submission time Handle Problem Language Result Execution time Memory
9855 2014-10-01T17:05:17 Z dohyun0324 Palindromes (APIO14_palindrome) C++
100 / 100
 748 ms 43572 KB 
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define M 300010
using namespace std;
long long dap;
int n,SA[20][M],arr[M],order[M],lcp[M],d[M*2],arr2[M*2],len[M],top,ch[30];
int p1[M],p2[M],st1[M],st2[M];
char a[M],s[M*2],b[M*2];
struct data
{
    int x,y,p;
    bool operator<(const data&r)const{
        if(x==r.x) return y<r.y;
        return x<r.x;
    }
}L[M];
void Suffix_Array()
{
    int i,j,k=1,cnt;
    for(i=1;i<=n;i++) ch[a[i]-'a'+1]=1;
    for(i=1;i<=26;i++) ch[i]+=ch[i-1];
    for(i=1;i<=n;i++) SA[0][i]=ch[a[i]-'a'+1];
    for(i=1;;i++)
    {
        if(k>n-1) break;
        for(j=1;j<=n;j++)
        {
            L[j].x=SA[i-1][j];
            if(j+k<=n) L[j].y=SA[i-1][j+k];
            else L[j].y=-1;
            L[j].p=j;
        }
        sort(L+1,L+n+1);
        cnt=0;
        for(j=1;j<=n;j++)
        {
            if(L[j].x!=L[j-1].x) SA[i][L[j].p]=++cnt;
            else if(L[j].y!=L[j-1].y) SA[i][L[j].p]=++cnt;
            else SA[i][L[j].p]=cnt;
        }
        k*=2;
    }
    for(j=1;j<=n;j++) arr[j]=SA[i-1][j];
}
void LCP()
{
    int i,j,k=0;
    for(i=1;i<=n;i++) order[arr[i]]=i;
    for(i=1;i<=n;i++)
    {
        if(arr[i]==1){k=0; continue;}
        if(k>0 && a[order[arr[i]-1]+k-1]!=a[order[arr[i]]+k-1]){k--; lcp[arr[i]]=k; continue;}
        for(j=k;j<=n;j++)
        {
            if(order[arr[i]-1]+j>n || order[arr[i]]+j>n || a[order[arr[i]-1]+j]!=a[order[arr[i]]+j]) break;
        }
        k=j;
        lcp[arr[i]]=k;
    }
}
void Manacher()
{
    int i,r=0,p=0;
    for(i=1;i<=n*2;i++)
    {
        if(r<i) d[i]=0;
        else d[i]=min(d[2*p-i],r-i);
        while(b[i+d[i]+1]==b[i-d[i]-1]) d[i]++;
        if(r<d[i]+i) r=d[i]+i, p=i;
    }
}
void solve()
{
    int i,big=0,pos,*q;
    for(i=1;i<=n*2;i++) arr2[(i-d[i])/2+1]=i;
    for(i=1;i<=n;i++)
    {
        if(big<arr2[i]) big=arr2[i];
        if(big%2==1) len[arr[i]]=((big/2+1)-i)*2+1;
        else len[arr[i]]=(big/2-i)*2+2;
    }
    st1[0]=-1;
    for(i=1;i<=n;i++)
    {
        while(st1[top]>=lcp[i]) top--;
        top++; st1[top]=lcp[i]; st2[top]=i;
        q=lower_bound(st1+1,st1+top+1,len[i]); pos=q-st1;
        p1[i]=st2[pos-1];
    }
    top=0;
    for(i=n;i>=1;i--)
    {
        while(st1[top]>=lcp[i+1]) top--;
        top++; st1[top]=lcp[i+1]; st2[top]=i;
        q=lower_bound(st1+1,st1+top+1,len[i]); pos=q-st1;
        p2[i]=st2[pos-1];
    }
    for(i=1;i<=n;i++)
    {
        if(dap<(long long)len[i]*(long long)(p2[i]-p1[i]+1)) dap=(long long)len[i]*(long long)(p2[i]-p1[i]+1);
    }
}
int main()
{
    int i;
    scanf("%s",a);
    n=strlen(a);
    for(i=n;i>=1;i--) a[i]=a[i-1]; a[0]=0;
    for(i=1;i<=n*2;i++){
        if(i%2==1) b[i]=a[i/2+1];
        else b[i]='#';
    }
    Suffix_Array();
    LCP();
    Manacher();
    solve();
    printf("%lld",dap);
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

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

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 43572 KB Output is correct - answer is '1249925001'
2 Correct 168 ms 43572 KB Output is correct - answer is '396337935'
3 Correct 132 ms 43572 KB Output is correct - answer is '2500050000'
4 Correct 148 ms 43572 KB Output is correct - answer is '1016525689'
5 Correct 180 ms 43572 KB Output is correct - answer is '99645'
6 Correct 168 ms 43572 KB Output is correct - answer is '78569380'
7 Correct 140 ms 43572 KB Output is correct - answer is '82810000'
8 Correct 200 ms 43572 KB Output is correct - answer is '3989'
9 Correct 184 ms 43572 KB Output is correct - answer is '125529616'
10 Correct 184 ms 43572 KB Output is correct - answer is '66664'

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 43572 KB Output is correct - answer is '11250075000'
2 Correct 480 ms 43572 KB Output is correct - answer is '894243195'
3 Correct 480 ms 43572 KB Output is correct - answer is '22499400004'
4 Correct 428 ms 43572 KB Output is correct - answer is '2958163321'
5 Correct 644 ms 43572 KB Output is correct - answer is '298935'
6 Correct 524 ms 43572 KB Output is correct - answer is '1210831209'
7 Correct 552 ms 43572 KB Output is correct - answer is '303195156'
8 Correct 748 ms 43572 KB Output is correct - answer is '11804'
9 Correct 728 ms 43572 KB Output is correct - answer is '11813'
10 Correct 636 ms 43572 KB Output is correct - answer is '262144'
11 Correct 488 ms 43572 KB Output is correct - answer is '3750025000'
12 Correct 740 ms 43572 KB Output is correct - answer is '184796836'