結果
問題 | No.1097 Remainder Operation |
ユーザー |
|
提出日時 | 2020-06-27 00:50:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 1,548 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 32,000 KB |
実行使用メモリ | 6,400 KB |
最終ジャッジ日時 | 2024-07-05 03:14:15 |
合計ジャッジ時間 | 2,784 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include<cstdio>long long a[100005];long long sum[100005];int vis[100005];int step[100005];long long pre[100005];long long getSum(int r,int k,int n){long long mask = r, res = 0;for(int i = 0; i < k; i++){res += a[mask];mask = (mask+a[mask])%n;}return res;}int main(){int n;scanf("%d",&n);for(int i = 0; i < n; i++) scanf("%lld",&a[i]);vis[0] = 1, step[0] = 0, sum[0] = 0;pre[step[0]] = sum[0];int u = 0;long long cycle = -1, start = -1;long long weight = 0;while(true){int v = (u+a[u])%n;if(vis[v]==1){cycle = step[u]+1-step[v];start = v;weight = sum[u]+a[u]-sum[v];break;}else{vis[v] = 1;step[v] = step[u]+1;sum[v] = sum[u]+a[u];pre[step[v]] = sum[v];u = v;}}//printf("start = %lld, cycle = %lld, weight = %lld\n",start,cycle,weight);int q;scanf("%d",&q);while(q--){long long k;scanf("%lld",&k);if(k<step[start]) printf("%lld\n",pre[k]);else{long long ans = 0;k -= step[start];ans += sum[start];long long cnt = k/cycle;//printf("ans = %lld, cnt = %lld\n",ans,cnt);ans += cnt*weight;long long left = k%cycle;ans += pre[step[start]+left]-pre[step[start]];printf("%lld\n",ans);}}return 0;}