結果

問題 No.464 PPAP
ユーザー YamyukiYamyuki
提出日時 2016-12-17 19:52:21
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,810 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 25,216 KB
実行使用メモリ 13,796 KB
最終ジャッジ日時 2024-05-08 04:12:04
合計ジャッジ時間 980 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
9,704 KB
testcase_01 AC 3 ms
11,752 KB
testcase_02 AC 2 ms
11,748 KB
testcase_03 AC 2 ms
11,752 KB
testcase_04 AC 2 ms
11,752 KB
testcase_05 AC 1 ms
11,752 KB
testcase_06 AC 2 ms
9,704 KB
testcase_07 AC 2 ms
11,760 KB
testcase_08 AC 2 ms
11,756 KB
testcase_09 AC 1 ms
9,704 KB
testcase_10 AC 2 ms
11,788 KB
testcase_11 AC 2 ms
11,784 KB
testcase_12 AC 2 ms
11,788 KB
testcase_13 AC 2 ms
11,792 KB
testcase_14 AC 2 ms
11,792 KB
testcase_15 AC 1 ms
11,748 KB
testcase_16 AC 2 ms
11,752 KB
testcase_17 AC 1 ms
13,796 KB
testcase_18 AC 1 ms
11,752 KB
testcase_19 AC 2 ms
11,752 KB
testcase_20 AC 2 ms
11,752 KB
testcase_21 AC 2 ms
11,756 KB
testcase_22 AC 2 ms
11,752 KB
testcase_23 AC 2 ms
11,920 KB
testcase_24 AC 2 ms
11,792 KB
testcase_25 AC 2 ms
11,788 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}
0