結果
問題 |
No.1097 Remainder Operation
|
ユーザー |
|
提出日時 | 2021-10-04 18:31:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 2,184 bytes |
コンパイル時間 | 2,363 ms |
コンパイル使用メモリ | 202,868 KB |
最終ジャッジ日時 | 2025-01-24 20:14:00 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector <int> adj[100005]; int A[100005]; vector <long long int> q; int n,m; long long int t; int history[100005]; long long int visited[100005][2]; long long int Left[100005]; long long int Right[100005]; int main(void) { cin.tie(0); ios::sync_with_stdio(false); cin >> n; for(int i=0;i<n;i++) { cin >> A[i]; adj[i].push_back((i + A[i])%n); } cin >> m; for(int i=0;i<m;i++) { cin >> t; q.push_back(t); } memset(visited,-1,sizeof(visited)); memset(history,-1,sizeof(history)); visited[0][0] = 0; visited[0][1] = 0; queue <int> que; que.push(0); int pos = -1; int pos2 = -1; while(!que.empty()) { int now = que.front(); que.pop(); for(auto next : adj[now]) { if(visited[next][0]==-1) { visited[next][1] = visited[now][1] + A[now]; visited[next][0] = visited[now][0] + 1; history[next] = now; que.push(next); } else { pos = next; pos2 = now; break; } } } long long int L = visited[pos][0]; long long int P = visited[pos2][0] - visited[pos][0] + 1; long long int SUM1 = visited[pos][1]; long long int SUM2 = visited[pos2][1] - visited[pos][1] + A[pos2]; { int cnt = 0; queue <int> que; que.push(0); Left[cnt] = 0; while(cnt<L) { int now = que.front(); que.pop(); Left[cnt+1] += Left[cnt]; Left[cnt+1] += A[now]; cnt++; for(auto next :adj[now]) { que.push(next); } } } { int cnt = 0; queue <int> que; que.push(pos); Right[cnt] = 0; while(cnt<P) { int now = que.front(); que.pop(); Right[cnt+1] += Right[cnt]; Right[cnt+1] += A[now]; cnt++; for(auto next :adj[now]) { que.push(next); } } } for(int i=0;i<q.size();i++) { long long int res = 0; if(q[i] < L) { res = Left[q[i]]; } else { res += SUM1; q[i]-=L; res += ((q[i]/P)*SUM2); q[i]%=P; res += Right[q[i]]; } cout << res << '\n'; } return 0; }