結果
問題 |
No.958 たぷりすたべる (回文)
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()