結果

問題 No.958 たぷりすたべる (回文)
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:54:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,689 bytes
コンパイル時間 1,203 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 120,252 KB
最終ジャッジ日時 2025-03-31 17:55:47
合計ジャッジ時間 9,507 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47 TLE * 1 -- * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    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 = [int(input[ptr + i]) for i in range(Q)]
    ptr += Q

    # Precompute mirror_max for each position c in 0..N-1
    N_original = N
    S2 = S + S  # Double the string to handle wrapping easily
    mirror_max = [0] * N

    for c in range(N):
        max_r = 0
        # Check up to N-1 steps. Since after that it repeats
        # We'll check until N steps to catch all possible mismatches
        # If no mismatch after N steps, then it's considered infinite
        is_infinite = True
        max_possible = N
        for i in range(1, max_possible + 1):
            left = (c - i) % (2*N)
            right = (c + i) % (2*N)
            if left >= 2*N or right >= 2*N:
                break
            if S2[left] != S2[right]:
                is_infinite = False
                break
            max_r = i
        if is_infinite:
            # Set to a large value (as max possible radius is up to 1e18)
            mirror_max[c] = 1 << 60  # Represents infinity
        else:
            mirror_max[c] = max_r

    for A in queries:
        x = A
        # Compute c in 0-based (x-1) mod N
        c = (x - 1) % N
        possible_mirror = mirror_max[c]
        # Compute boundary constraints
        left_max = x - 1
        right_max = K * N - x
        boundary_r = min(left_max, right_max)
        # Actual radius is the minimum of the two
        r = min(possible_mirror, boundary_r)
        print(2 * r + 1)

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