結果
問題 |
No.1097 Remainder Operation
|
ユーザー |
![]() |
提出日時 | 2020-06-27 11:00:41 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 235 ms / 2,000 ms |
コード長 | 1,244 bytes |
コンパイル時間 | 2,019 ms |
コンパイル使用メモリ | 197,592 KB |
最終ジャッジ日時 | 2025-01-11 12:41:22 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #define M_PI 3.14159265358979323846 // pi using namespace std; typedef long long ll; typedef unsigned long long ull; typedef vector<ll> VI; typedef pair<ll, ll> P; typedef tuple<ll, ll, ll> t3; typedef tuple<ll, ll, ll, ll> t4; typedef tuple<ll, ll, ll, ll, ll> t5; #define rep(a,n) for(ll a = 0;a < n;a++) #define repi(a,b,n) for(ll a = b;a < n;a++) using namespace std; static const ll INF = 1e15; const ll mod = 1000000007; int main() { int n; cin >> n; vector<ll> vs(n); rep(i, n) cin >> vs[i]; vector<ll> x(n+1, 0); vector<ll> prevIndex(n, -1); prevIndex[0] = 0; ll loop = 0; ll loopUnit = 0; ll loopStart = 0; ll loopEnd = 0; for (int i = 1; i <= n+1; i++) { ll r = x[i-1] + vs[x[i-1] % n]; x[i] = r; if (prevIndex[x[i] % n] != -1) { loopStart = prevIndex[x[i] % n]; loopEnd = i; loop = loopEnd - loopStart; loopUnit = x[loopEnd] - x[loopStart]; break; } prevIndex[x[i] % n] = i; } int q; cin >> q; vector<ll> ans; rep(_, q) { ll k; cin >> k; if (k <= loopEnd) { ans.push_back(x[k]); continue; } ans.push_back(x[(k - loopStart) % loop + loopStart] + (k-loopStart)/loop * loopUnit); } rep(i, q) { cout << ans[i] << endl; } return 0; }