結果
問題 | No.1097 Remainder Operation |
ユーザー |
![]() |
提出日時 | 2020-08-12 02:39:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 452 ms / 2,000 ms |
コード長 | 1,508 bytes |
コンパイル時間 | 1,007 ms |
コンパイル使用メモリ | 97,620 KB |
実行使用メモリ | 100,400 KB |
最終ジャッジ日時 | 2024-10-09 12:27:24 |
合計ジャッジ時間 | 8,748 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <algorithm>#include <cmath>#include <cstdint>#include <cstdio>#include <iomanip>#include <iostream>#include <map>#include <queue>#include <set>#include <stack>#include <string>#include <vector>using namespace std;#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)#define All(v) (v).begin(), (v).end()#define pb push_back#define MP(a, b) make_pair((a), (b))using ll = long long;using pii = pair<int, int>;using pll = pair<ll, ll>;const int INF = 1 << 30;const ll LINF = 1LL << 60;const int MOD = 1e9 + 7;int main() {int N;cin >> N;vector<ll> A(N);rep(i, N) cin >> A[i];vector<vector<ll>> to(61, vector<ll>(N));vector<vector<ll>> sum(61, vector<ll>(N));rep(i, N) {to[0][i] = (i + A[i]) % N;sum[0][i] = A[i];}// to[i][j]:=jからスタートして2^i回後の場所// sum[i][j]:=jからスタートして2^i回後に足される値for(int k = 0; k < 60; k++) {for(int i = 0; i < N; i++) {to[k + 1][i] = to[k][to[k][i]];sum[k + 1][i] = sum[k][i] + sum[k][to[k][i]];}}int Q;cin >> Q;rep(i, Q) {ll K;cin >> K;int cur = 0;ll res = 0;for(int k = 60; k >= 0; k--) {if(K & (1LL << k)) {res += sum[k][cur];cur = to[k][cur];}}cout << res << endl;}return 0;}