結果
問題 | No.1013 〇マス進む |
ユーザー |
![]() |
提出日時 | 2020-03-20 22:14:09 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 267 ms / 2,000 ms |
コード長 | 1,147 bytes |
コンパイル時間 | 1,581 ms |
コンパイル使用メモリ | 174,156 KB |
実行使用メモリ | 53,632 KB |
最終ジャッジ日時 | 2024-12-15 06:17:16 |
合計ジャッジ時間 | 11,385 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long int; using ull = unsigned long long int; using P = pair<ll, ll>; using P3 = pair<double,P>; using PP = pair<P, P>; constexpr int INF = 1 << 30; constexpr ll MOD = ll(1e9)+7; constexpr int di[] = {0, 1, 0, -1}; constexpr int dj[] = {1, 0, -1, 0}; constexpr double EPS = 1e-9; int main(){ int N, K; cin >> N >> K; vector<int> p(N); for(int i=0;i<N;i++){ cin >> p[i]; } vector<vector<P> > dp(31, vector<P>(N)); // dp[k][i] マスiから2**k回移動したときの(マスのindex,移動数) for(int i=0;i<N;i++){ dp[0][i] = P((i+p[i])%N, p[i]); } for(int k=0;k<30;k++){ for(int i=0;i<N;i++){ ll idx = dp[k][i].first, cnt = dp[k][i].second; dp[k+1][i] = P(dp[k][idx].first, dp[k][idx].second+cnt); } } for(int i=0;i<N;i++){ ll ans = i+1; int now = i; for(int k=0;k<=30;k++){ if((K>>k)&1){ ans += dp[k][now].second; now = dp[k][now].first; } } cout << ans << endl; } return 0; }