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