結果

問題 No.1097 Remainder Operation
コンテスト
ユーザー CPer
提出日時 2026-10-06 22:03:24
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,922 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,552 ms
コンパイル使用メモリ 356,136 KB
実行使用メモリ 9,928 KB
最終ジャッジ日時 2026-10-06 22:03:31
合計ジャッジ時間 6,536 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//  Created On : 2026-10-06 17:48:16

#include <cassert>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define returnNO  {std::cout << "NO\n";  return;}
#define returnYES {std::cout << "YES\n"; return;}
#define returnAns(x) {cout << x << "\n"; return;}

template<typename T>
using MaxHeap = std::priority_queue<T, std::vector<T>, std::less<T>>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

const int MOD1 = 1000000007;
const int MOD2 = 998244353;


/** obs **
1. first chain and then cycle
2. compute X % N -> add arr[r] to X

**/


void solve(int test_case_index) {  
    int n; cin >> n;
    vector<int> arr(n, 0); for (int& a : arr) cin >> a;

    ll X = 0;
    vector<bool> vis(n, false);
    vector<int> ans; ans.reserve(n);
    auto walkCycle = [&] () -> int {
        while (true) {
            int r = X % n;
            if (vis[r]) return r;
            vis[r] = true, X += arr[r];
            ans.push_back(arr[r]);
        }
    };
    int start = walkCycle();

    ll len = 1; X += arr[X % n];
    while (((X) % n) != start) len += 1, X += arr[X % n];

    vector<ll> psum(n + 1, 0); 
    for (int i = 1; i <= n; ++i) psum[i] = psum[i - 1] + ans[i - 1];

    auto calcAns = [&] (ll k) -> ll {
        ll chain_len = n - len;
        ll chain_ans = psum[min(chain_len, k)];
        k -= min(chain_len, k);

        ll cycles = k / len, rem = k % len;
        ll cycle_ans = cycles * (psum[n] - psum[n - len]) 
                     + (psum[n - len + rem] - psum[n - len]);
        return chain_ans + cycle_ans;
    };


    int q; cin >> q;
    while (q--) {
        ll k; cin >> k;
        cout << calcAns(k) << "\n";
    }
}



void preComp() {

}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    preComp();

    int t = 1;
    // std::cin >> t;

    for (int i = 1; i <= t; ++i) solve(i);
    return 0;
}
0