結果
問題 |
No.1013 〇マス進む
|
ユーザー |
|
提出日時 | 2020-07-10 16:42:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 303 ms / 2,000 ms |
コード長 | 1,200 bytes |
コンパイル時間 | 1,605 ms |
コンパイル使用メモリ | 174,200 KB |
実行使用メモリ | 161,996 KB |
最終ジャッジ日時 | 2024-10-11 00:27:22 |
合計ジャッジ時間 | 13,994 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) using namespace std; using ll = long long ; using P = pair<int,int> ; using pll = pair<long long,long long>; constexpr int INF = 1e9; constexpr long long LINF = 1e17; constexpr int MOD = 1000000007; constexpr double PI = 3.14159265358979323846; int main(){ ll n,k; cin >> n >> k; vector<ll> p(n); rep(i,n) cin >> p[i]; vector<vector<pll>> db(100,vector<pll>(n)); rep(i,n) db[0][i] = {(i+p[i])%n,(i+p[i])/n}; for(int i=1;i<=99;i++){ rep(j,n){ ll a = db[i-1][j].first; ll b = db[i-1][j].second + db[i-1][a].second; a = db[i-1][a].first; db[i][j] = pll(a,b); } } vector<pll> ans(n); rep(i,n) ans[i] = pll(i,0); ll c = 0; while(k > 0){ if(k&1){ rep(i,n){ ll a = ans[i].first; ll b = ans[i].second + db[c][a].second; a = db[c][a].first; ans[i] = pll(a,b); } } k >>= 1; ++c; } rep(i,n){ ll now = ans[i].first + ans[i].second * n + 1 ; cout << now << endl; } return 0; }