結果

問題 No.465 PPPPPPPPPPPPPPPPAPPPPPPPP
コンテスト
ユーザー bal4u
提出日時 2019-08-15 16:48:41
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 89 ms / 2,000 ms
コード長 3,134 bytes
コンパイル時間 508 ms
コンパイル使用メモリ 32,128 KB
実行使用メモリ 10,496 KB
最終ジャッジ日時 2024-09-19 15:21:48
合計ジャッジ時間 1,765 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
}

//// 回文の最長半径を求める
#if 0
void manacher(int *rad, char *s, int n) {
    int l, r, c = 0;
    for (r = 0; r < n; r++) {
        l = (c << 1) - r;
        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;
        }
    }
}
#else
void manacher(int *rad, char *s, int n) {
	int i = 0, j = 0, k;
	while (i < n) {
		while (i >= j && i+j < n && s[i-j] == s[i+j]) j++;
		rad[i] = j;
		k = 1;
		while (i >= k && i+k < n && k+rad[i-k] < j) rad[i+k] = rad[i-k], k++;
		i += k; j -= k;
	}
}
#endif

#define MAX 1000010
#define LIM 7000
char S[MAX]; int W;
int  rad[MAX];
int  pp1[MAX], wp1;
int  pp3_[MAX], *pp3, 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;
}

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

int bsGE3(int x) {
	int m, l = 0, r = wp3;
    while (l < r) {
        m = (l+r) >> 1;
        if (pp3[m] < x) l = m + 1; else r = m;
    }
	return l;
}

int main()
{
	int i, p1, p3, w, w3;
	ll ans;
	
	W = ins(S);
	manacher(rad, S, W);
	
	// 回文であるP1, P3
	p1 = 1, p3 = W >> 1;
	for (i = 1; i < W; i+=2) {
		if (i < p1 + rad[p1]) pp1[wp1++] = i;
		if (i > p3 - rad[p3]) pp3_[wp3++] = i;
		p1++, p3++;
	}
	while (pp1[wp1-1] >= W-7) wp1--;
	i = 0; while (pp3_[i] < 7) i++, wp3--;
	pp3 = pp3_+i;
	

	if (wp1 == wp3 && wp1 > LIM) {
		// 繰り返しパターンへの対策
		// aaaa, ababab, abaabaaba 等
		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 >= w) {
			ans = (ll)wp1*(wp1+1)*(wp1+2) / 6;
			if (pp1[1]-pp1[0] != d) ans--;
			printf("%lld\n", ans);
			return 0;
		}
	}

	ans = 0;
	w = W-5, w3 = W-4; for (i = 3; i < w; i++) {
		int l, r;
		
		// P2がiを中心としたときの、P1の末尾位置の範囲[l,r]
		if (i-rad[i] <= 1) l = 0; else l = bsGE1(i-rad[i]);
		r = bsLE(l, i-2+(i&1));

		// P2の末尾がP3と重なっているか
		while (l <= r) {
			int w = (i<<1) - pp1[l++];
			if (w > w3);  // P2の末尾によって (P1, P2, A, P3) が作れないケース
			else if (w >= pp3[0]) ans += wp3 - bsGE3(w+2);  // P3の領域に侵入したケース
			else { ans += (ll)(r-l+2) * wp3; break; }  // P3と重ならないケース
		}
	}
	printf("%lld\n", ans);
	return 0;
}
0