結果
問題 |
No.1013 〇マス進む
|
ユーザー |
![]() |
提出日時 | 2025-03-20 12:40:11 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 251 ms / 2,000 ms |
コード長 | 1,393 bytes |
コンパイル時間 | 549 ms |
コンパイル使用メモリ | 82,652 KB |
実行使用メモリ | 142,392 KB |
最終ジャッジ日時 | 2025-03-20 12:40:25 |
合計ジャッジ時間 | 13,217 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
def main(): import sys input = sys.stdin.read().split() ptr = 0 N, K = int(input[ptr]), int(input[ptr+1]) ptr += 2 P = list(map(int, input[ptr:ptr+N])) ptr += N max_level = 30 # Sufficient for K up to 1e9 next_table = [[0] * (N + 1) for _ in range(max_level)] sum_table = [[0] * (N + 1) for _ in range(max_level)] # Initialize for level 0 for i in range(1, N + 1): p = P[i - 1] s_next = (i + p - 1) % N s_next += 1 # Convert back to 1-based next_table[0][i] = s_next sum_table[0][i] = p # Precompute higher levels using binary lifting for j in range(1, max_level): for i in range(1, N + 1): prev_next = next_table[j-1][i] next_table[j][i] = next_table[j-1][prev_next] sum_table[j][i] = sum_table[j-1][i] + sum_table[j-1][prev_next] result = [] for i in range(1, N + 1): current = i total = 0 remaining = K for j in reversed(range(max_level)): if remaining >= (1 << j): total += sum_table[j][current] current = next_table[j][current] remaining -= (1 << j) if remaining == 0: break result.append(str(i + total)) print('\n'.join(result)) if __name__ == '__main__': main()