結果
問題 | No.1097 Remainder Operation |
ユーザー |
![]() |
提出日時 | 2020-06-26 22:28:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 232 ms / 2,000 ms |
コード長 | 5,523 bytes |
コンパイル時間 | 3,021 ms |
コンパイル使用メモリ | 197,720 KB |
最終ジャッジ日時 | 2025-01-11 11:49:23 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)#define itn int#define miele(v) min_element(v.begin(), v.end())#define maele(v) max_element(v.begin(), v.end())#define SUM(v) accumulate(v.begin(), v.end(), 0LL)#define lb(a, key) lower_bound(a.begin(),a.end(),key)#define ub(a, key) upper_bound(a.begin(),a.end(),key)#define COUNT(a, key) count(a.begin(), a.end(), key)#define BITCOUNT(x) __builtin_popcount(x)#define pb push_back#define all(x) (x).begin(),(x).end()#define F first#define S secondusing P = pair <int,int>;using WeightedGraph = vector<vector <P>>;using UnWeightedGraph = vector<vector<int>>;using Real = long double;using Point = complex<Real>; //Point and Vector2d is the same!using Vector2d = complex<Real>;const long long INF = 1LL << 60;const int MOD = 1000000007;const double EPS = 1e-15;const double PI=3.14159265358979323846;template <typename T>int getIndexOfLowerBound(vector <T> &v, T x){return lower_bound(v.begin(),v.end(),x)-v.begin();}template <typename T>int getIndexOfUpperBound(vector <T> &v, T x){return upper_bound(v.begin(),v.end(),x)-v.begin();}template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }#define DUMPOUT cerr#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)istream &operator>>(istream &is, Point &p) {Real a, b; is >> a >> b; p = Point(a, b); return is;}template <typename T, typename U>istream &operator>>(istream &is, pair<T,U> &p_var) {is >> p_var.first >> p_var.second;return is;}template <typename T>istream &operator>>(istream &is, vector<T> &vec) {for (T &x : vec) is >> x;return is;}template <typename T, typename U>ostream &operator<<(ostream &os, pair<T, U> &pair_var) {DUMPOUT<<'{';os << pair_var.first;DUMPOUT<<',';os << " "<< pair_var.second;DUMPOUT<<'}';return os;}template <typename T>ostream &operator<<(ostream &os, vector<T> &vec) {DUMPOUT<<'[';for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");DUMPOUT<<']';return os;}template <typename T>ostream &operator<<(ostream &os, vector<vector<T>> &df) {for (auto& vec : df) os<<vec;return os;}template <typename T, typename U>ostream &operator<<(ostream &os, map<T, U> &map_var) {DUMPOUT << "{";repi(itr, map_var) {os << *itr;itr++;if (itr != map_var.end()) DUMPOUT << ", ";itr--;}DUMPOUT << "}";return os;}template <typename T>ostream &operator<<(ostream &os, set<T> &set_var) {DUMPOUT << "{";repi(itr, set_var) {os << *itr;itr++;if (itr != set_var.end()) DUMPOUT << ", ";itr--;}DUMPOUT << "}";return os;}void print() {cout << endl;}template <class Head, class... Tail>void print(Head&& head, Tail&&... tail) {cout << head;if (sizeof...(tail) != 0) cout << " ";print(forward<Tail>(tail)...);}void dump_func() {DUMPOUT << '#'<<endl;}template <typename Head, typename... Tail>void dump_func(Head &&head, Tail &&... tail) {DUMPOUT << head;if (sizeof...(Tail) > 0) DUMPOUT << ", ";dump_func(std::move(tail)...);}#ifdef DEBUG_#define DEB#define dump(...) \DUMPOUT << " " << string(#__VA_ARGS__) << ": " \<< "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" \<< endl \<< " ", \dump_func(__VA_ARGS__)#else#define DEB if (false)#define dump(...)#endifvector <int> a;int n;int sim(int k){int res = 0;while(k--){res += a[(res)%n];}return res;}signed main(void) { cin.tie(0); ios::sync_with_stdio(false);cin>>n;a.resize(n);cin>>a;int q; cin>>q;// shuukiを求めようint now = 0;int shuuki = 0, sum = 0, first = 0, cnt = 0, fcnt = 0; //周期のsumint x=0;vector <int> cost(n);vector <int> vis(n);vector <int> place;while(!vis[now]){cnt++;vis[now] = cnt;x += a[now];cost[now] += x;place.pb(now);int ne = (x)%n;now = ne;}place.pb(now);first = cost[now], fcnt = vis[now];unsigned long long cirsum = x + a[now] - cost[now];vector <int> cir;int now2 = (a[now] + now) % n;vector <int> cdata;x = 0;while(now2 != now){x += a[now2];cdata.pb(x);cir.pb(now2);now2 = (a[now2] + now2) % n;}x += a[now2];cdata.pb(x);cir.pb(now2);dump(cir);rep(i, q){int k; cin>>k;if(k <= 5000){print(sim(k));}else if(k <= place.size()){print(cost[place[k-1]]);}else {unsigned long long ans = 0;k -= fcnt;ans += first;unsigned long long mawarukaisu = k / cir.size();k %= cir.size();ans += mawarukaisu * cirsum;if(k != 0){ans += cdata[k-1];}print(ans);}}}