結果
問題 | No.1097 Remainder Operation |
ユーザー |
![]() |
提出日時 | 2020-08-09 21:12:02 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 141 ms / 2,000 ms |
コード長 | 2,334 bytes |
コンパイル時間 | 2,331 ms |
コンパイル使用メモリ | 206,068 KB |
最終ジャッジ日時 | 2025-01-12 19:31:44 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; /////////////////////////////////////////// const long long int INF = 1LL<<60; const long long int Mod = 1000000007; using ll = long long int; using ci = const int; using vi = vector<int>; using Vi = vector<long long int>; using P = pair<int, int>; using PLL = pair<ll, ll>; using matrix = vector<vector<ll>>; #define pb(x) push_back(x) #define mp(x,y) make_pair(x,y) #define all(x) (x).begin(),(x).end() #define rp(i,N) for(ll i = 0; i < (ll)N; i++) #define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i) template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; } template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; } template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根; #define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート #define p_queue(v) priority_queue<v, vector<v>, greater<v> > template<class T> inline void princ(T x){cout<<x<<" ";}; template<class T> inline void print(T x){cout<<x<<"\n";}; template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; } template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; } /////////////////////////////////////////////////////////////////////////////////// void solve(){ ll n; cin >> n; Vi a(n); rp(i,n) cin >> a.at(i); ll x=0; vi visit(n,-1); map<ll,ll> ma; ll ctr=0; ll syuki; ll start,end; while(1){ if(visit[x%n]>=0){ ma[ctr]=x; syuki=ctr-visit[x%n]; start=visit[x%n]; end=ctr; break; } visit[x%n]=ctr; ma[ctr]=x; x+=a[x%n]; ctr++; } ll q; cin >> q; Vi ans; while(q--){ ll k; cin >> k; if(k<end){ ans.pb(ma[k]); }else{ ll loop=(k-start)/syuki; ans.pb((ma[end]-ma[start])*loop+ma[(k-start)%syuki+start]); } } for(auto an:ans){ print(an); } return; } int main(){ cin.tie(0);ios::sync_with_stdio(false); std::cout<<std::fixed<<std::setprecision(30); solve(); return 0; }