結果

問題 No.2858 Make a Palindrome
ユーザー prd_xxxprd_xxx
提出日時 2024-08-25 16:23:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,177 bytes
コンパイル時間 356 ms
コンパイル使用メモリ 82,504 KB
実行使用メモリ 137,188 KB
最終ジャッジ日時 2024-08-25 16:23:54
合計ジャッジ時間 11,758 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 838 ms
77,976 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 AC 342 ms
78,152 KB
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 148 ms
112,656 KB
testcase_22 WA -
testcase_23 AC 171 ms
117,956 KB
testcase_24 AC 157 ms
115,660 KB
testcase_25 WA -
testcase_26 AC 143 ms
114,820 KB
testcase_27 AC 188 ms
132,508 KB
testcase_28 WA -
testcase_29 AC 184 ms
137,188 KB
testcase_30 AC 181 ms
132,996 KB
testcase_31 WA -
testcase_32 AC 185 ms
133,232 KB
testcase_33 AC 183 ms
132,992 KB
testcase_34 AC 199 ms
132,752 KB
testcase_35 AC 219 ms
133,248 KB
testcase_36 AC 189 ms
132,716 KB
testcase_37 AC 182 ms
133,244 KB
testcase_38 WA -
testcase_39 AC 185 ms
132,920 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def manacher(_S):
    L = 2*len(_S)+1
    radius = [0]* L
    S = ['#'] * L
    for i in range(len(_S)):
        S[2*i+1] = _S[i]
    i = j = 0
    while i < L:
        while i-j >= 0 and i+j < L and S[i-j] == S[i+j]:
            j += 1
        radius[i] = j
        k = 1
        while i-k >= 0 and i+k < L and k+radius[i-k] < j:
            radius[i+k] = radius[i-k]
            k += 1
        i += k
        j -= k
    return radius

def solve(N,M,S):
    m1 = manacher(S)
    for i,m in enumerate(m1):
        if i%2 == 0:
            l = m - 1
        else:
            l = (m//2)*2 - 1
        if l >= M: return 1
    m2 = manacher(S+S)
    for i,m in enumerate(m2):
        if i%2 == 0:
            l = m - 1
        else:
            l = (m//2)*2 - 1
        if l >= M: return 2
    m3 = manacher(S+S+S)
    maxl = 0
    for i,m in enumerate(m3):
        if i%2 == 0:
            l = m - 1
        else:
            l = (m//2)*2 - 1
        if l >= M: return 3
        maxl = max(maxl,l)
    if maxl >= N:
        return 0--M//N
    else:
        return -1

T = int(input())
for _ in range(T):
    N,M = map(int,input().split())
    S = input()
    print(solve(N,M,S))
0