結果
問題 |
No.1013 〇マス進む
|
ユーザー |
👑 ![]() |
提出日時 | 2024-09-09 17:12:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 97 ms / 2,000 ms |
コード長 | 2,683 bytes |
コンパイル時間 | 1,072 ms |
コンパイル使用メモリ | 84,708 KB |
最終ジャッジ日時 | 2025-02-24 06:20:47 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 62 |
ソースコード
#include <vector> #include <cassert> namespace po167{ template<class T, T(*op)(T, T)> struct Doubling_op{ int n; int depth; std::vector<std::vector<int>> index; std::vector<std::vector<T>> val; Doubling_op(std::vector<int> p, std::vector<T> v, long long lim = (1ll << 60) - 1){ n = p.size(); for (auto x : p) assert(0 <= x && x < n); assert(n == (int)v.size()); depth = 1; while ((1ll << depth) <= lim) depth++; index.resize(depth); val.resize(depth); index[0] = p; val[0] = v; for (int i = 1; i < depth; i++){ index[i].resize(n); val[i].resize(n); for (int j = 0; j < n; j++){ int tmp = index[i - 1][j]; index[i][j] = index[i - 1][tmp]; val[i][j] = op(val[i - 1][j], val[i - 1][tmp]); } } } std::pair<int, T> query(int start_ind, T start_val, long long times){ assert(0 <= times && times < (1ll << depth)); int i = 0; while (times){ if (times & 1){ start_val = op(start_val, val[i][start_ind]); start_ind = index[i][start_ind]; } i++; times >>= 1; } return std::make_pair(start_ind, start_val); } }; struct Doubling{ int n; int depth; std::vector<std::vector<int>> index; Doubling(std::vector<int> p, long long lim = (1ll << 60) - 1){ n = p.size(); for (auto x : p) assert(0 <= x && x < n); depth = 1; while ((1ll << depth) <= lim) depth++; index.resize(depth); index[0] = p; for (int i = 1; i < depth; i++){ index[i].resize(n); for (int j = 0; j < n; j++){ index[i][j] = index[i - 1][index[i - 1][j]]; } } } int query(int ind, long long times){ assert(0 <= times && times < (1ll << depth)); int i = 0; while (times){ if (times) ind = index[i][ind]; i++; times >>= 1; } return ind; } }; } long long op(long long a, long long b){ return a + b; } #include <iostream> int main(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int N, K; std::cin >> N >> K; std::vector<long long> P(N); std::vector<int> Q(N); for (int i = 0; i < N; i++){ std::cin >> P[i]; Q[i] = (i + P[i]); if (Q[i] >= N) Q[i] -= N; } po167::Doubling_op<long long, op> D(Q, P, K); for (int i = 0; i < N; i++){ std::cout << D.query(i, i + 1, K).second << "\n"; } }