結果
問題 | No.1097 Remainder Operation |
ユーザー |
![]() |
提出日時 | 2020-10-20 16:44:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 944 ms / 2,000 ms |
コード長 | 1,613 bytes |
コンパイル時間 | 851 ms |
コンパイル使用メモリ | 87,888 KB |
実行使用メモリ | 164,224 KB |
最終ジャッジ日時 | 2024-07-21 08:23:40 |
合計ジャッジ時間 | 8,288 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 21 |
ソースコード
#include <iostream>#include <string>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <map>#include <numeric>using namespace std;using ll = long long;#define REP(i,n) for(ll i=0;i<(ll)(n);i++)#define REPD(i,n) for(ll i=n-1;i>=0;i--)#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)#define input(...) __VA_ARGS__; in(__VA_ARGS__)#if __has_include("debugger.cpp")#include "debugger.cpp"#elsevoid print() {std::cout << std::endl;}template <class Head, class... Tail>void print(Head&& head, Tail&&... tail) {cout << head;if (sizeof...(tail) > 0) cout << " ";print(std::forward<Tail>(tail)...);}# endifvoid in() { }template <class Head, class... Tail>void in(Head&& head, Tail&&... tail) {cin >> head;in(std::forward<Tail>(tail)...);}vector<ll> a;ll n;struct Ret {ll position, over;};vector<vector<Ret>> table;#define DP table[i][k]Ret dfs(ll i, ll k) {i %= n;if (DP.position != -1) return DP;if (k == 0) return DP = {(i + a[i]) % n, a[i] + i};Ret left = dfs(i, k - 1);Ret right = dfs(left.position, k - 1);return DP = {right.position, left.over + right.over - left.position};}int main() {cin >> n;a = vector<ll>(n);REP(i, n) cin >> a[i];ll input(q);table = vector<vector<Ret>>(n + 1, vector<Ret>(100, {-1, -1}));REP(j, q) {ll input(k);ll t = 1;while (1ll << t < k) t++;ll ans = 0;REP(i, t + 1) {if (k & 1) {ans = dfs(ans, i).over + (ans - ans % n);}k >>= 1;}print(ans);}}