結果
問題 | No.1097 Remainder Operation |
ユーザー |
![]() |
提出日時 | 2020-06-26 21:43:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 1,334 bytes |
コンパイル時間 | 2,017 ms |
コンパイル使用メモリ | 193,736 KB |
最終ジャッジ日時 | 2025-01-11 11:08:59 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}int dx[4]={0,1,-1,0};int dy[4]={1,0,0,-1};long double eps = 1e-6;long double pi = acos(-1);signed main(){ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(20);ll n;cin>>n;ll a[n];for(int i=0;i<n;i++){cin>>a[i];}ll cnt[n+2]={};cnt[0] = 0;ll now = 0;int r = 0;int used[n+2]={};used[0] = 1;ll cy = -1;ll st = -1;int las = 0;for(int i=1;i<=n;i++){now += a[r];r = (r+a[r])%n;if(used[r]){st = used[r]-1;cy = i+1 - used[r];cnt[i] = now;las = i;break;}used[r] = i+1;cnt[i] = now;}int q;cin>>q;while(q--){ll k; cin>>k;if(k <= st){cout << cnt[k] << "\n";continue;}ll ans = cnt[st];k -= st;ans += (cnt[las] - cnt[st]) * (k/cy);k %= cy;ans += cnt[st+k] - cnt[st];cout << ans << "\n";}cerr << 61919700120 << endl;}