結果
問題 | 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 // piusing 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;}