結果
問題 |
No.1097 Remainder Operation
|
ユーザー |
|
提出日時 | 2020-06-26 23:13:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 235 ms / 2,000 ms |
コード長 | 1,201 bytes |
コンパイル時間 | 1,010 ms |
コンパイル使用メモリ | 82,920 KB |
最終ジャッジ日時 | 2025-01-11 12:08:48 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #define rep(i, j, n) for (i64 i = (j); i < (n); ++i) #define rrep(i, j, n) for (i64 i = (n)-1; i >= (j); --i) using namespace std; using i64 = int64_t; constexpr int INF = 1 << 30; int main() { int n, q; cin >> n; int *a = new int[n]; rep(i, 0, n) cin >> a[i]; cin >> q; vector<int> map(n, 0); rep(i, 0, n) map[i] = (a[i] + i) % n; vector<int> used(n, 0); used[0] = true; int now = 0; i64 cycle = 0; i64 len = 0; i64 cval = 0; i64 lval = 0; vector<i64> val; vector<i64> cv; val.push_back(0); cv.push_back(0); while (true) { ++len; lval += a[now]; val.push_back(lval); now = map[now]; if (used[now] == 1) { ++cycle; cval += a[now]; cv.push_back(cval); } if (used[now] == 2) break; ++used[now]; } i64 path = len - cycle; rep(i, 0, q) { i64 k; cin >> k; if (k <= len) cout << val[k] << '\n'; else { i64 ans = lval; i64 rem = k - len; ans += rem / cycle * cval; ans += cv[rem % cycle]; cout << ans << '\n'; } } delete[] a; return 0; }