結果

問題 No.464 PPAP
ユーザー YamyukiYamyuki
提出日時 2016-12-17 19:52:21
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,810 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 28,136 KB
実行使用メモリ 12,148 KB
最終ジャッジ日時 2023-08-20 21:56:55
合計ジャッジ時間 1,774 ms
ジャッジサーバーID
(参考情報)
judge13 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
12,048 KB
testcase_01 AC 2 ms
12,056 KB
testcase_02 AC 3 ms
12,064 KB
testcase_03 AC 3 ms
12,096 KB
testcase_04 AC 3 ms
12,048 KB
testcase_05 AC 3 ms
12,048 KB
testcase_06 AC 3 ms
12,008 KB
testcase_07 AC 3 ms
12,076 KB
testcase_08 AC 3 ms
12,012 KB
testcase_09 AC 3 ms
11,988 KB
testcase_10 AC 4 ms
12,140 KB
testcase_11 AC 3 ms
12,008 KB
testcase_12 AC 4 ms
12,036 KB
testcase_13 AC 3 ms
12,148 KB
testcase_14 AC 3 ms
12,008 KB
testcase_15 AC 3 ms
11,984 KB
testcase_16 AC 3 ms
12,000 KB
testcase_17 AC 3 ms
12,100 KB
testcase_18 AC 3 ms
11,964 KB
testcase_19 AC 3 ms
12,004 KB
testcase_20 AC 3 ms
11,976 KB
testcase_21 AC 3 ms
12,112 KB
testcase_22 AC 3 ms
11,988 KB
testcase_23 AC 3 ms
12,144 KB
testcase_24 AC 4 ms
12,068 KB
testcase_25 AC 4 ms
12,024 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:65:3: warning: implicit declaration of function ‘memset’ [-Wimplicit-function-declaration]
   memset(ns,0,sizeof(ns));
   ^~~~~~
main.c:65:3: warning: incompatible implicit declaration of built-in function ‘memset’
main.c:65:3: note: include ‘<string.h>’ or provide a declaration of ‘memset’
main.c:4:1:
+#include <string.h>
 
main.c:65:3:
   memset(ns,0,sizeof(ns));
   ^~~~~~
main.c:113:3: warning: implicit declaration of function ‘memcpy’ [-Wimplicit-function-declaration]
   memcpy(start,ns,sizeof(ns));
   ^~~~~~
main.c:113:3: warning: incompatible implicit declaration of built-in function ‘memcpy’
main.c:113:3: 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;
}
0