結果
問題 |
No.958 たぷりすたべる (回文)
|
ユーザー |
![]() |
提出日時 | 2020-05-12 01:44:01 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 933 ms / 2,000 ms |
コード長 | 809 bytes |
コンパイル時間 | 162 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 45,948 KB |
最終ジャッジ日時 | 2024-07-19 13:06:44 |
合計ジャッジ時間 | 15,941 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 53 |
ソースコード
import sys read = sys.stdin.buffer.read readline = sys.stdin.buffer.readline readlines = sys.stdin.buffer.readlines def Manacher(S): L = len(S) R = [0] * L i = 0; j = 0 while i < L: while (i >= j) and (i + j < L) and (S[i-j] == S[i+j]): j += 1 R[i] = j k = 1 while (i >= k) and (i + k < L) and (k + R[i-k] < j): R[i + k] = R[i - k] k += 1 i += k j -= k return R N,K,Q = map(int, readline().split()) S = readline().rstrip() A = map(int, read().split()) M = Manacher(S*3) for x in A: x -= 1 nl = x + 1 nr = N * K - x q, r = divmod(x, N) l = M[N + r] if l in [N + r + 1, 2 * N - r]: n = min(nl, nr) print(2 * n - 1) else: print(2 * min(l, nl, nr) - 1)