結果

問題 No.1013 〇マス進む
ユーザー lam6er
提出日時 2025-03-20 20:19:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 263 ms / 2,000 ms
コード長 1,393 bytes
コンパイル時間 191 ms
コンパイル使用メモリ 82,464 KB
実行使用メモリ 142,232 KB
最終ジャッジ日時 2025-03-20 20:21:03
合計ジャッジ時間 11,899 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

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()
0