結果

問題 No.1013 〇マス進む
コンテスト
ユーザー betrue12
提出日時 2020-03-20 21:49:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 344 ms / 2,000 ms
コード長 855 bytes
コンパイル時間 2,910 ms
コンパイル使用メモリ 194,832 KB
最終ジャッジ日時 2025-01-09 08:29:51
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> P(2*N), pos(N+1);
    for(int i=0; i<N; i++){
        cin >> P[i];
        pos[P[i]] = i;
        P[i+N] = P[i];
    }
    static int dub[32][100000];
    static int64_t gain[32][100000];
    for(int i=0; i<N; i++){
        dub[0][i] = pos[P[i+P[i]]];
        gain[0][i] = P[i];
    }
    for(int k=0; k<30; k++) for(int i=0; i<N; i++){
        dub[k+1][i] = dub[k][dub[k][i]];
        gain[k+1][i] = gain[k][i] + gain[k][dub[k][i]];
    }
    for(int i=0; i<N; i++){
        int p = i;
        int64_t ans = i+1;
        for(int k=0; k<30; k++) if(nth_bit(K, k)){
            ans += gain[k][p];
            p = dub[k][p];
        }
        cout << ans << endl;
    }
    return 0;
}
0