結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
ユーザー bal4ubal4u
提出日時 2019-08-15 14:02:49
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 92 ms / 2,000 ms
コード長 2,411 bytes
コンパイル時間 965 ms
コンパイル使用メモリ 31,872 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-09-19 15:16:40
合計ジャッジ時間 1,817 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 17 ms
6,528 KB
testcase_07 AC 5 ms
5,376 KB
testcase_08 AC 20 ms
6,400 KB
testcase_09 AC 31 ms
6,656 KB
testcase_10 AC 29 ms
6,656 KB
testcase_11 AC 20 ms
6,528 KB
testcase_12 AC 15 ms
5,376 KB
testcase_13 AC 11 ms
5,376 KB
testcase_14 AC 17 ms
6,656 KB
testcase_15 AC 84 ms
7,552 KB
testcase_16 AC 90 ms
8,192 KB
testcase_17 AC 92 ms
8,320 KB
testcase_18 AC 12 ms
7,936 KB
testcase_19 AC 14 ms
10,496 KB
testcase_20 AC 23 ms
6,656 KB
testcase_21 AC 50 ms
6,656 KB
32_ratsliveonnoevilstar.txt AC 13 ms
8,704 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:26: note: in expansion of macro 'gc'
   18 |                 if ((c = gc()) <= ' ') break;
      |                          ^~

ソースコード

diff # 

// yukicoder: No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
// bal4u 2019.8.15

#include <stdio.h>

typedef long long ll;

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

int ins(char *s) { // 文字列の特殊入力
	char *p = s; int c;
	*s++ = '_';	while (1) {
		if ((c = gc()) <= ' ') break;
		*s++ = c, *s++ = '_';
	}
	*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 1000010
#define LIM 7000
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);
	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++;
	}

	if (wp1 == wp3 && wp1 > LIM) {
		int d = pp1[2]-pp1[1], w = wp1-1;
		for (i = 2; i < w; i++) {
			if (pp1[i]-pp1[i-1] != d ||	pp3[i]-pp3[i-1] != d) break;
		}
		if (i >= wp1-1) {
			ans = (ll)wp1*(wp1+1)*(wp1+2) / 6;
			if (pp1[1]-pp1[0] != d) ans--;
			printf("%lld\n", ans);
			return 0;
		}
	}

	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