結果
問題 | No.2858 Make a Palindrome |
ユーザー |
|
提出日時 | 2024-08-25 15:59:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 413 ms / 3,000 ms |
コード長 | 1,819 bytes |
コンパイル時間 | 163 ms |
コンパイル使用メモリ | 82,168 KB |
実行使用メモリ | 99,576 KB |
最終ジャッジ日時 | 2024-08-25 15:59:51 |
合計ジャッジ時間 | 10,218 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
import sysinput = lambda :sys.stdin.readline()[:-1]ni = lambda :int(input())na = lambda :list(map(int,input().split()))yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")#######################################################################def manacher(s):s = s.replace('', '#')n = len(s)p = [1 for _ in range(n)]c = 0for i in range(1, n):if i < c + p[c]:p[i] = min(p[c - (i - c)], c + p[c] - i)while i - p[i] >= 0 and i + p[i] < n and s[i - p[i]] == s[i + p[i]]:p[i] += 1if i + p[i] > c + p[c]:c = ireturn pdef max_palindrome(s):P = manacher(s)return max(P) - 1def solve(n, m, s):A = max_palindrome(s)B = max_palindrome(s + s)C = max_palindrome(s + s + s)if A >= m:return 1elif B >= m:return 2elif C >= m:return 3elif B == C and B < m:return -1else:return 3 + (m - B - 1) // (C - B)def greedy(n, m, s):z = ""for t in range(1000):if max_palindrome(z) >= m:return tz += sreturn -1for _ in range(ni()):n, m = na()s = input()print(solve(n, m, s))#print(greedy(n, m, s))# from random import randint# for _ in range(10000):# n = randint(1, 10)# m = randint(1, n * 10)# s = "".join([chr(randint(97, 122)) for _ in range(n)])# if solve(n, m, s) != greedy(n, m, s):# print(n, m)# print(s)# print(solve(n, m, s))# print(greedy(n, m, s))# break# #print(_)# n, m = na()# s = input()# print(solve(n, m, s))# z = s# for i in range(4):# print(*manacher(z))# z += s