結果
問題 | No.2858 Make a Palindrome |
ユーザー |
![]() |
提出日時 | 2024-07-15 11:49:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,012 ms / 3,000 ms |
コード長 | 1,066 bytes |
コンパイル時間 | 225 ms |
コンパイル使用メモリ | 82,192 KB |
実行使用メモリ | 353,792 KB |
最終ジャッジ日時 | 2024-07-15 11:49:48 |
合計ジャッジ時間 | 21,623 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
# taken from https://tjkendev.github.io/procon-library/python/string/manacher.htmldef manacher(S):C = []for a in S:C.append(a)C.append(0)C.pop()L = len(C)R = [0]*Li = j = 0while i < L:while j <= i < L-j and C[i-j] == C[i+j]:j += 1R[i] = jk = 1while j-R[i-k] > k <= i < L-k:R[i+k] = R[i-k]k += 1i += k; j -= kfor i in range(L):if i & 1 == R[i] & 1:R[i] -= 1return Rdef longest_palindrome(s):return max(manacher(s))def solve(n, m, s):v1 = longest_palindrome(s * 1)v2 = longest_palindrome(s * 2)v3 = longest_palindrome(s * 3)v4 = longest_palindrome(s * 4)if v1 >= m:return 1if v2 >= m:return 2if v3 >= m:return 3ans = -1if v3 >= 2 * n:subans = 3 + (m - v3 + 2 * n - 1) // (2 * n) * 2ans = (subans if ans == -1 else min(ans, subans))if v4 >= 2 * n:subans = 4 + (m - v4 + 2 * n - 1) // (2 * n) * 2ans = (subans if ans == -1 else min(ans, subans))return anst = int(input())for _ in range(t):n, m = map(int, input().split())s = input()print(solve(n, m, s))