結果

問題 No.958 たぷりすたべる (回文)
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 18:41:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,693 bytes
コンパイル時間 313 ms
コンパイル使用メモリ 82,164 KB
実行使用メモリ 132,296 KB
最終ジャッジ日時 2025-06-12 18:41:45
合計ジャッジ時間 7,800 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 WA * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

def is_palindrome(s):
    n = len(s)
    for i in range(n // 2):
        if s[i] != s[n - 1 - i]:
            return False
    return True

def manachers(s):
    t = '#' + '#'.join(s) + '#'
    n = len(t)
    p = [0] * n
    c = r = 0
    for i in range(n):
        mirror = 2 * c - i
        if i < r:
            p[i] = min(r - i, p[mirror])
        a, b = i + p[i] + 1, i - p[i] - 1
        while a < n and b >= 0 and t[a] == t[b]:
            p[i] += 1
            a += 1
            b -= 1
        if i + p[i] > r:
            c = i
            r = i + p[i]
    return p

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N = int(input[ptr])
    ptr += 1
    K = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    S = input[ptr]
    ptr += 1
    queries = []
    for _ in range(Q):
        queries.append(int(input[ptr]))
        ptr += 1
    
    if is_palindrome(S):
        max_len = K * N
        for x in queries:
            d = min(x - 1, max_len - x)
            print(2 * d + 1)
        return
    
    SS = S + S
    manacher_result = manachers(SS)
    d_circular = [0] * N
    n_ss = len(SS)
    t_len = len(manacher_result)
    for pos in range(N):
        center = pos + N
        real_center = 2 * center + 1
        if real_center >= t_len:
            expansion = 0
        else:
            expansion = manacher_result[real_center]
        d_circular[pos] = expansion
    
    max_len = K * N
    for x in queries:
        pos_in_S = (x - 1) % N
        d_char = d_circular[pos_in_S]
        d_bound = min(x - 1, max_len - x)
        d = min(d_char, d_bound)
        print(2 * d + 1)

if __name__ == '__main__':
    main()
0