結果

問題 No.464 PPAP
ユーザー bal4u
提出日時 2019-08-15 11:22:38
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 1 ms / 2,000 ms
コード長 2,300 bytes
コンパイル時間 148 ms
コンパイル使用メモリ 31,616 KB
実行使用メモリ 6,940 KB
最終ジャッジ日時 2024-09-19 15:04:39
合計ジャッジ時間 864 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

// yukicoder: No.464 PPAP
// bal4u 2019.8.15

#include <stdio.h>

typedef long long ll;

//// 入出力関係
#if 0
#define gc() getchar_unlocked()
#else
#define gc() getchar()
#endif

int spa;
int ins(char *s) { // 文字列の特殊入力
	char *p = s; int c;
	*s++ = '_', spa = c = gc(), *s++ = c, *s++ = '_';
	while (1) {
		if ((c = gc()) <= ' ') break;
		*s++ = c, *s++ = '_';
		if (spa > 0 && c != spa) spa = -1;
	}
	*s = 0;
	return s - p;
}

//// 回文の最長半径を求める
void manacher(int *rad, char *s, int n) {
    int l, r, c = 0;
    for (r = 0; r < n; r++) {
        l = (c << 1) - r;   // l = c - (r - c);
        if (r + rad[l] < c + rad[c]) rad[r] = rad[l];
        else {
            int rr = c + rad[c];
            int rl = (r << 1) - rr;
            while (rl >= 0 && rr < n && s[rl] == s[rr]) rr++, rl--;
            rad[r] = rr - r;
            c = r;
        }
    }
}

#define MAX 10010
char S[MAX]; int W;
int  rad[MAX];
int  pp1[MAX], wp1;
int  pp3[MAX], wp3;

// 見つからなければ、一つ小さい要素を返す
int bsLE(int l, int x)
{
	int m, r = wp1;
    while (l < r) {
        m = (l+r) >> 1;
        if (pp1[m] <= x) l = m + 1; else r = m;
    }
	return l-1;
}

// 見つからなければ、一つ大きい要素を返す。つまり、 >= x
int bsGE(int *pp, int x, int r) {
	int m, l = 0;
    while (l < r) {
        m = (l+r) >> 1;
        if (pp[m] < x) l = m + 1; else r = m;
    }
	return l;
}

int main()
{
	int i, cp1, cp3, w1, w3;
	ll ans;
	
	W = ins(S);
	if (spa > 0) {  // 同じ文字の列
		W >>= 1;
		printf("%lld\n", (ll)(W-3)*(W-2)*(W-1)/6);
		return 0;
	}
	
//	printf("W:%d, %s\n", W, S);
	manacher(rad, S, W);
	
	// 回文であるP1, P3
	w1 = W-7, cp1 = 1;
	w3 = 7, cp3 = W >> 1;
	for (i = 1; i < W; i+=2) {
		if (i < w1 && i < cp1 + rad[cp1]) pp1[wp1++] = i;
		if (i >= w3 && i > cp3 - rad[cp3]) pp3[wp3++] = i;
		cp1++, cp3++;
	}
	
	ans = 0;
	w1 = W-5, w3 = W-4; for (i = 3; i < w1; i++) {
		int j, l, r;
		if (i-rad[i] <= 1) l = 0; else l = bsGE(pp1, i-rad[i], wp1);
		r = bsLE(l, i-2+(i&1));
		for (j = l; j <= r; j++) {
			int w = (i<<1) - pp1[j];
			if (w > w3);
			else if (w >= pp3[0]) ans += wp3 - bsGE(pp3, w+2, wp3);
			else {
				ans += (ll)(r-j+1) * wp3;
				break;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}
0