結果

問題 No.464 PPAP
ユーザー bal4ubal4u
提出日時 2019-08-15 10:02:22
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 2,243 bytes
コンパイル時間 1,116 ms
コンパイル使用メモリ 31,508 KB
実行使用メモリ 4,348 KB
最終ジャッジ日時 2023-10-19 18:41:26
合計ジャッジ時間 2,078 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,348 KB
testcase_01 AC 1 ms
4,348 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 1 ms
4,348 KB
testcase_05 AC 1 ms
4,348 KB
testcase_06 AC 1 ms
4,348 KB
testcase_07 AC 1 ms
4,348 KB
testcase_08 AC 1 ms
4,348 KB
testcase_09 AC 1 ms
4,348 KB
testcase_10 AC 1 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 3 ms
4,348 KB
testcase_13 AC 1 ms
4,348 KB
testcase_14 AC 1 ms
4,348 KB
testcase_15 AC 1 ms
4,348 KB
testcase_16 AC 1 ms
4,348 KB
testcase_17 AC 1 ms
4,348 KB
testcase_18 AC 1 ms
4,348 KB
testcase_19 AC 1 ms
4,348 KB
testcase_20 AC 1 ms
4,348 KB
testcase_21 AC 1 ms
4,348 KB
testcase_22 AC 1 ms
4,348 KB
testcase_23 AC 1 ms
4,348 KB
testcase_24 AC 1 ms
4,348 KB
testcase_25 AC 1 ms
4,348 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function 'ins':
main.c:10:14: warning: implicit declaration of function 'getchar_unlocked' [-Wimplicit-function-declaration]
   10 | #define gc() getchar_unlocked()
      |              ^~~~~~~~~~~~~~~~
main.c:18:35: note: in expansion of macro 'gc'
   18 |         *s++ = '_', *s++ = same = gc(), *s++ = '_';
      |                                   ^~

ソースコード

diff # 

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

#include <stdio.h>

typedef long long ll;

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

int same;
int ins(char *s) { // 文字列の特殊入力
	char *p = s, c;
	*s++ = '_', *s++ = same = gc(), *s++ = '_';
	while (1) {
		c = gc(), *s++ = c, *s++ = '_';
		if (c < ' ') break;
		if (same >= 0 && c != same) same = -1;
	}
	s -= 2, *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 - (rr - r);
            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, p1, p3, cp1, cp3, w1, w3;
	ll ans;
	
	W = ins(S);
	if (same > 0) {  // 同じ文字の列
		W >>= 1;
		printf("%lld\n", (ll)(W-3)*(W-2)*(W-1)/6);
		return 0;
	}
	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; for (i = 3; i < w1; i++) {
		int j, l, r, w;
		if (i - rad[i] <= 1) l = 0; else l = bsGE(pp1, i-rad[i], wp1);
		r = bsLE(l, (i&1)? i-1: i-2);
		for (j = l; j <= r; j++) {
			if ((w = (i<<1) - pp1[j]) > W-4) continue;
			if (w < pp3[0]) ans += wp3;
			else ans += (wp3-bsGE(pp3, w+2, wp3));
		}
	}
	printf("%lld\n", ans);	
		
	return 0;
}
0