結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー Yamyuki
提出日時 2016-12-17 19:58:48
言語 C90
(gcc 12.3.0)
結果
AC  
実行時間 88 ms / 2,000 ms
コード長 2,810 bytes
コンパイル時間 679 ms
コンパイル使用メモリ 25,088 KB
実行使用メモリ 25,344 KB
最終ジャッジ日時 2024-12-23 15:09:24
合計ジャッジ時間 2,652 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:65:17: warning: implicit declaration of function ‘memset’ [-Wimplicit-function-declaration]
   65 |                 memset(ns,0,sizeof(ns));
      |                 ^~~~~~
main.c:4:1: note: include ‘<string.h>’ or provide a declaration of ‘memset’
    3 | #include<limits.h>
  +++ |+#include <string.h>
    4 | 
main.c:65:17: warning: incompatible implicit declaration of built-in function ‘memset’ [-Wbuiltin-declaration-mismatch]
   65 |                 memset(ns,0,sizeof(ns));
      |                 ^~~~~~
main.c:65:17: note: include ‘<string.h>’ or provide a declaration of ‘memset’
main.c:113:17: warning: implicit declaration of function ‘memcpy’ [-Wimplicit-function-declaration]
  113 |                 memcpy(start,ns,sizeof(ns));
      |                 ^~~~~~
main.c:113:17: note: include ‘<string.h>’ or provide a declaration of ‘memcpy’
main.c:113:17: warning: incompatible implicit declaration of built-in function ‘memcpy’ [-Wbuiltin-declaration-mismatch]
main.c:113:17: note: include ‘<string.h>’ or provide a declaration of ‘memcpy’

ソースコード

diff #
プレゼンテーションモードにする

#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
long n;
char str[500001];
long s[1000000];
long b[500000];
long start[32],ns[32];
long delta[32],nd[32];
long num[32],nn[32];
long pre[500000],suf[500000];
long ep[500000],dp[500000];
void manacher(void){
    long i=0,j=0,k;
    while(i<n*2){
        while(i-j>=0 && i+j+1<n*2 && str[(i-j)/2]==str[(i+j+1)/2]){
            j++;
        }
        s[i]=j;
        k=1;
        while(i-k>=0 && s[i]-k>=0 && s[i-k]!=s[i]-k){
            s[i+k]=min(s[i-k],s[i]-k);
            k++;
        }
        i+=k;
        j=max(j-k,0);
    }
}
int main(){
    long i,I,g,g1,g2,g3,j,lv,r;
    long long ans=0;
    str[0]=getchar();
    n=0;
    while(str[n]!='\n'){
        n++;
        str[n]=getchar();
    }
    manacher();
    for(i=0;i<n;i++){
        if(s[i]==i+1){
            pre[i]=1;
        }
    }
    I=LONG_MAX;
    g=0;
    for(i=0;i<n;i++){
        //printf("loop %ld\n",i);
        g1=0;
        for(j=0;j<g;j++){
            if(start[j]-1>=0 && str[start[j]-1]==str[i]){
                //printf("cont s: %ld d: %ld n: %ld \n",start[j]-1,delta[j],num[j]);
                start[j]--;
                start[g1]=start[j];
                delta[g1]=delta[j];
                num[g1]=num[j];
                g1++;
            }
        }
        memset(ns,0,sizeof(ns));
        memset(nd,0,sizeof(nd));
        memset(nn,0,sizeof(nn));
        g2=0;
        for(j=0;j<g1;j++){
            if((j==0 && delta[j]==I) || (g2-1>=0 && ns[g2-1]+nd[g2-1]*(nn[g2-1]-1)==start[j]-delta[j])){
                ns[g2]=start[j];
                nd[g2]=delta[j];
                nn[g2]=num[j];
                g2++;
                continue;
            }
            ns[g2]=start[j];
            nd[g2]=(g2==0)?I:start[j]-(ns[g2-1]+nd[g2-1]*(nn[g2-1]-1));
            nn[g2]=1;
            g2++;
            
            if(num[j]>1){
                ns[g2]=start[j]+delta[j];
                nd[g2]=delta[j];
                nn[g2]=num[j]-1;
                g2++;
            }
        }
        if(i-1>=0 && str[i-1]==str[i]){
            ns[g2]=i-1;
            nd[g2]=(0<g2)?(i-1-(ns[g2-1]+nd[g2-1]*(nn[g2-1]-1))):I;
            nn[g2]=1;
            g2++;
        }
        //printf("add %ld s: %ld d: %ld n: 1\n",g2,i,(0<g2)?i-(ns[g2-1]+nd[g2-1]*(nn[g2-1]-1)):I);
        ns[g2]=i;
        nd[g2]=(0<g2)?(i-(ns[g2-1]+nd[g2-1]*(nn[g2-1]-1))):I;
        nn[g2]=1;
        g2++;
        g3=0;
        for(j=0;j<g2;j++){
            if(j==0 || nd[j]!=nd[j-1]){
                //printf("%ld s: %ld d: %ld n: %ld\n",g3,ns[j],nd[j],nn[j]);
                ns[g3]=ns[j];
                nd[g3]=nd[j];
                nn[g3]=nn[j];
                g3++;
            }else{
                //printf("merge %ld\n",g3-1);
                nn[g3-1]+=nn[j];
            }
        }
        memcpy(start,ns,sizeof(ns));
        memcpy(delta,nd,sizeof(nd));
        memcpy(num,nn,sizeof(nn));
        g=g3;
        for(j=0;j<g;j++){
            r=start[j]+delta[j]*(num[j]-1);
            lv=0;
            if(r-1>=0) lv+=pre[r-1];
            if(num[j]>1 && start[j]-delta[j]>=0){
                lv+=ep[start[j]-delta[j]];
            }
            //printf("%ld\n",lv);
            dp[i]+=lv;
            if(delta[j]<=start[j]){
                ep[start[j]-delta[j]]=lv;
            }
        }
        //printf("g %ld\n",g);
    }
    for(i=0;i<n;i++){
        if(s[n*2-2-i]==i+1){
            suf[n-1-i]=1;
        }
    }
    for(i=1;i<n;i++){
        suf[n-1-i]+=suf[n-i];
    }
    for(i=0;i<n-2;i++){
        ans+=(long long)dp[i]*(long long)suf[i+2];
    }
    printf("%lld\n",ans);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0