結果
問題 | No.1097 Remainder Operation |
ユーザー |
![]() |
提出日時 | 2024-09-09 16:49:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 375 ms / 2,000 ms |
コード長 | 10,670 bytes |
コンパイル時間 | 2,906 ms |
コンパイル使用メモリ | 233,016 KB |
最終ジャッジ日時 | 2025-02-24 06:20:24 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#pragma GCC optimize("Ofast,unroll-loops")#include <bits/stdc++.h>#include <iostream>#include <map>#include <set>using namespace std;#include <vector>using std::vector;template <class T>using vc = vector<T>;template <class T>using vvc = vc<vc<T>>;template <class T>using vvvc = vc<vvc<T>>;template <class T>using vvvvc = vc<vvvc<T>>;#define VC(T, a, ...) auto a = vector<T>(__VA_ARGS__)#define VVC(T, a, n, ...) \auto a = vector(n, vector<T>(__VA_ARGS__));#define VVVC(T, a, n, m, ...) \auto a = vector(n, vector(m, vector<T>(__VA_ARGS__)));#define VVVVC(T, a, n, m, l, ...) \auto a = \vector(n, vector(m, vector(l, vector<T>(__VA_ARGS__))));#define be begin()#define en end()#define all(a) (a).be, (a).en#define rbe rbegin()#define ren rend()#define allr(a) a.rbe, a.ren#include <algorithm>using std::sort;template<class A>void sort(A& a) { sort(all(a)); }#include <algorithm>using std::sort;template<class A>void sortr(A& a) { sort(allr(a)); }#include <algorithm>using std::reverse;template<class A>void reverse(A& a) { reverse(all(a)); }#define eval_0(a, ...) a#define eval_1(a, b, ...) b#define eval_2(a, b, c, ...) c#define eval_3(a, b, c, d, ...) d#define eval_4(a, b, c, d, e, ...) e#define eval_5(a, b, c, d, e, f, ...) f#define eval_6(a, b, c, d, e, f, g, ...) g#define iter_1(a, A) for (auto&& a : A)#define iter_2(a, b, A) for (auto&& [a, b] : A)#define iter_3(a, b, c, A) for (auto&& [a, b, c] : A)#define iter_4(a, b, c, d, A) for (auto&& [a, b, c, d] : A)#define iter_5(a, b, c, d, e, A) \for (auto&& [a, b, c, d, e] : A)#define iter(...) \eval_6(__VA_ARGS__, iter_5, iter_4, iter_3, iter_2, iter_1)( \__VA_ARGS__ \)#define pb push_back#define eb emplace_back#define emp emplace#include <numeric>using std::accumulate;template<class T, class U>T sum(const vc<U>& a) { return accumulate(all(a), T(0)); }#define loop while (1)using ll = long long;#define FOR_1(i, n) for (int i = 0; i < n; i++)#define FOR_2(i, a, b) for (ll i = a; i < b; i++)#define FOR_3(i, a, b, c) for (ll i = a; i < b; i += c)#define FOR(...) \eval_4(__VA_ARGS__, FOR_3, FOR_2, FOR_1, rep)(__VA_ARGS__)#define FORR_1(i, n) for (int i = n; i-- > 0;)#define FORR_2(i, l, r) for (ll i = r; i-- > l;)#define FORR_3(i, l, r, d) for (ll i = r - 1; i >= l; i -= c)#define FORR(...) \eval_4(__VA_ARGS__, FORR_3, FORR_2, FORR_1)(__VA_ARGS__)#define rep(t) for (int __ = 0; __ < t; ++__)template <class T, class F>T binary_search(F f, T ok, T ng) {while (abs(ok - ng) > 1) {T x = (ok + ng) / 2;(f(x) ? ok : ng) = x;}return ok;}#include <algorithm>using std::lower_bound;using std::upper_bound;template<class A, class T>auto lb(A& a, const T& x) { return lower_bound(all(a), x); }template<class A, class T>int lbi(const A& a, const T& x) { return lb(a, x) - a.be; }template<class A, class T>auto ub(A& a, const T& x) { return upper_bound(all(a), x); }template<class A, class T>int ubi(const A& a, const T& x) { return ub(a, x) - a.be; }#include <string>using std::string;using str = string;template<class A>int len(const A& a) { return a.size(); }#include <iostream>using std::cout;#define yesno(y, n) \void y(bool f = 1) { cout << (f ? #y : #n) << '\n'; } \void n(bool f = 1) { y(!f); }yesno(yes, no);yesno(Yes, No);yesno(YES, NO);template<class T=int>vc<T> iota(int n, T v=0) {vc<T> a(n);iota(all(a), v);return a;}#include <utility>using std::pair;using pii = pair<int, int>;#include <utility>using std::pair;using pll = pair<ll, ll>;using vii = vc<pii>;using vll = vc<pll>;#define mt make_tuple#define ins inserttemplate <class T, class U>bool chmax(T& a, const U& b) { return b > a ? a = b, 1 : 0; }template <class T, class U>bool chmin(T& a, const U& b) { return b < a ? a = b, 1 : 0; }using dbl = double;using ld = long double;#include <tuple>using std::tuple;template <class... T>using tup = tuple<T...>;#include <queue>using std::priority_queue;template<class T>using max_que = priority_queue<T>;using std::greater;template<class T>using min_que = priority_queue<T, vc<T>, greater<T>>;template<class T>T pop(min_que<T>& q) { T v = q.top(); q.pop(); return v; }template<class T>T pop(max_que<T>& q) { T v = q.top(); q.pop(); return v; }#include <algorithm>using std::max_element;using std::min_element;template <class A>auto max(const A& a) { return *max_element(all(a)); }template <class A>auto min(const A& a) { return *min_element(all(a)); }template <class T>T max(const set<T>& s) {return *s.rbe;}template <class T>T min(const set<T>& s) {return *s.be;}template <class T>T max(const multiset<T>& s) {return *s.rbe;}template <class T>T min(const multiset<T>& s) {return *s.be;}#include <bits/stdc++.h>using namespace std;template <typename... T>constexpr auto min(T... a) {using U = common_type_t<T...>;return std::min(initializer_list<U>{a...});}template <typename... T>constexpr auto max(T... a) {using U = common_type_t<T...>;return std::max(initializer_list<U>{a...});}#define fi first#define se second#include <functional>using std::function;template <class F>using fn = function<F>;template <class A>A fancy(const A& a, const vc<int>& p) {int n = len(p);A b(n);FOR(i, n) b[i] = a[p[i]];return b;}template <class A>vc<int> argsort(const A& a) {auto p = iota(len(a));sort(all(p), [&](int i, int j) {return a[i] == a[j] ? i < j : a[i] < a[j];});return p;}vc<int> argperm(const vc<int>& p) {int n = len(p);vc<int> a(n);FOR(i, n) a[p[i]] = i;return a;}template <class A>vc<int> rankify(const A& a) {return argperm(argsort(a));}/* deprecated*/#include <queue>using std::queue;template<class T>T pop(queue<T>& q) {T x = q.front();q.pop();return x;}#include <queue>using std::deque;template <class T>T pop_front(deque<T>& q) {T x = q.front();q.pop_front();return x;}template <class T>T pop_back(deque<T>& q) {T x = q.back();q.pop_back();return x;}template <class T>T pop(vc<T>& a) {T x = a.back();a.pop_back();return x;}class range {ll i, b, d;public:range(ll a, ll b, ll d): i(a), b(b), d(d) {}range(ll a, ll b): range(a, b, a < b ? 1 : -1) {}range(int n): range(0, n) {}range& begin() { return *this; }range& end() { return *this; }range& operator++() {i += d;return *this;}bool operator!=(const range&) const {return d > 0 && i < b || d < 0 && i > b;}ll operator*() const { return i; }};template <class T>int signum(T x) {return x > 0 ? 1 : x < 0 ? -1 : 0;}#include <random>using std::mt19937_64;using std::random_device;mt19937_64 mrand(random_device{}());int rng(int x) { return mrand() % x; }constexpr double PI = acos(-1);#include <iostream>using namespace std;void fastio() {ios::sync_with_stdio(0);cin.tie(0);}template <class T, class U>istream& operator>>(istream& i, pair<T, U>& p) {return i >> p.fi >> p.se;}#include <tuple>#include <iostream>using namespace std;template <int k = 0, class T>void scan_tup(istream& i, T& x) {if constexpr (tuple_size<T>::value > k) {i >> get<k>(x);scan_tup<k + 1>(i, x);}}template <class... T>istream& operator>>(istream& i, tuple<T...>& x) {scan_tup(i, x);return i;}template <class I, class T>I& operator>>(I& i, vc<T>& a) {iter(x, a) i >> x;return i;}#include <iostream>using namespace std;template <typename... T>void scan(T&... a) { (cin >> ... >> a); }#define VEC(T, a, n) VC(T, a, n); cin >> a;#define V(T, a, n) VC(T, a, n); cin >> a;#define VV(T, a, n, m) VVC(T, a, n, m); cin >> a;#define VVV(T, a, n, m, l) VVC(T, a, n, m, l); cin >> a;#define INT(...) int __VA_ARGS__; scan(__VA_ARGS__)#define LL(...) ll __VA_ARGS__; scan(__VA_ARGS__)#define DBL(...) dbl __VA_ARGS__; scan(__VA_ARGS__)#define VI(a, n) V(int, a, n)#define VL(a, n) V(ll, a, n)#define VII(a, n) V(pii, a, n)#define VLL(a, n) V(pll, a, n)#define VSTR(a, n) V(str, a, n)template <class T, size_t n>ostream& operator<<(ostream& os, const array<T, n>& a) {FOR(i, n) {if (i) os << ' ';os << a[i];}return os;}template <class T, size_t n>ostream& operator<<(ostream& os, array<array<T, n>, n> a) {FOR(i, n) os << a[i] << '\n';return os;}#include <bits/stdc++.h>using namespace std;template <class T, class U>ostream& operator<<(ostream& o, pair<T, U>& p) {return o << p.fi << ' ' << p.se;}#include <bits/stdc++.h>using namespace std;template <int k = 0, class T>void out_tup(ostream& o, T& x) {if constexpr (tuple_size<T>::value > k) {if constexpr (k > 0) o << ' ';o << get<k>(x);out_tup<k + 1>(o, x);}}template <class... T>ostream& operator<<(ostream& o, tuple<T...>& x) {out_tup(o, x);return o;}template <class O, class T>O& operator<<(O& o, vc<T> a) {FOR(i, len(a)) {if (i) o << ' ';o << a[i];}return o;}template <class O, class T>O& operator<<(O& o, vvc<T> a) {iter(x, a) o << x << '\n';return o;}#include <iostream>using namespace std;template <class T, class... U>void print(T a, U... b) {cout << a;((cout << ' ' << b), ...);cout << '\n';}template <class T, T (*op)(T, T), T (*e)()>class doubling {vvc<int> f;vvc<T> x;int h;public:doubling(const vc<int>& _f, const vc<T>& _x, int h = 60): h(h) {int n = len(_f);assert(len(_x) == n);f.assign(h, vc<int>(n, -1));x.assign(h, vc<T>(n, e()));f[0] = _f;x[0] = _x;FOR(i, h - 1) FOR(j, n) {int k = f[i][j];if (k == -1) {f[i + 1][j] = -1;x[i + 1][j] = x[i][j];continue;}f[i + 1][j] = f[i][k];x[i + 1][j] = op(x[i][j], x[i][k]);}}pair<int, T> jump(int i, ll k) {assert(k >= 0);T y = e();int j = 0;while (k && i != -1) {if (k & 1) {y = op(y, x[j][i]);i = f[j][i];}k >>= 1;j++;}return {i, y};}template <class F>ll max_step(F g, int i) {T y = e();if (!g(i, y)) return -1;ll k = 0;FORR(j, h) {int ii = f[j][i];if (ii == -1) continue;T yy = op(y, x[j][i]);if (!g(ii, yy)) continue;k |= 1ll << j;i = ii;y = yy;}return k;}};ll op(ll x, ll y) {return x + y;}ll e() { return 0; }int main() {int n;cin >> n;vc<ll> a(n);cin >> a;vc<int> f(n);FOR(i, n) f[i] = (i + a[i]) % n;doubling<ll, op, e> fg(f, a, 40);INT(q);rep(q) {ll k;cin >> k;cout << fg.jump(0, k).se << '\n';}}