Introduction

CCPC 2021 Online E - Monopoly asks for the earliest arrival time in a process that repeats forever. With direct simulation, there is no clear bound on the number of laps. Only the positions within a single lap form a finite set; every complete lap changes the score by the same cycle sum.

The Problem

The board contains $n$ integers $a_1,a_2,\ldots,a_n$ arranged in a circle. The initial score is $0$. The first step lands on $a_1$, and movement then continues cyclically in order, adding the value at the current position to the score at every step.

Each query gives a target score $x$. Output the number of steps when the score first becomes exactly $x$, or $-1$ if it cannot be reached. The initial state already has score $0$, so the answer for $x=0$ is $0$.

For one test case, $n,m\le 10^5$. Across all test cases, the sums of $n$ and $m$ are each at most $5\times 10^5$. The target score can have absolute value as large as $10^{12}$, so enumerating steps or complete cycles is infeasible.

Positions Within a Cycle

Define the prefix sums of the first lap:

The score change over one complete lap is:

In the implementation, pre[i] stores the within-cycle prefix $P_i$ ($0\le i<n$), while s stores the total $S$ of one complete cycle.

Any step count can be written uniquely as:

Here, $q$ is the number of completed laps, and $i$ is the number of steps already taken in the current lap. The score is:

Keep only $P_0$ through $P_{n-1}$. $P_n=S$ and $P_0$ at the start of the next lap represent the same cycle boundary. Keeping both would give two representations of the same time.

For a query $x$, we now need to find a within-cycle position $i$ satisfying:

while minimizing $q\cdot n+i$.

A Zero Cycle Sum

If $S=0$, a complete lap does not change the score:

Every reachable score already appears in the first lap. For each prefix sum, record only the earliest step where it occurs, then answer queries by looking it up in a hash table. The initial prefix $P_0=0$ corresponds to step $0$.

Later occurrences of the same prefix sum have larger step counts and cannot improve the answer.

f1st stores this mapping from prefix sum to earliest position. When building it, insert a prefix sum only on its first occurrence, so solve1 naturally retrieves the earliest step:

1
2
3

if (!f1st.count(s)) {
    f1st[s] = i;
}

Grouping by Congruence Class

Now consider $S\ne 0$, and let:

Complete cycles change the score by integer multiples of $d$. A necessary condition for a within-cycle prefix $P_i$ to produce the target $x$ is:

Group the prefixes by their nonnegative remainder modulo $d$. For a fixed remainder $r$, write:

Congruence ensures that the required number of laps is an integer. The remaining constraint is $q\ge 0$. The sign of the cycle sum determines which side of the sorted array contains the valid prefixes.

In the implementation, mod normalizes negative remainders to $[0,d)$, and same_rem stores candidate prefixes by remainder. Each candidate’s first component is $P_i$; its second component, val, stores the corresponding step-count adjustment in each of the two cases below.

A Positive Cycle Sum

Here, $S=d$. Substituting into:

gives:

The validity condition is:

The corresponding number of steps is:

For a fixed query, $h\cdot n$ is constant. Sort the prefixes within each congruence class by $P_i$ in ascending order, and maintain prefix minima of:

For a query, binary-search for the last prefix no greater than $x$ and retrieve the minimum through that position.

In the implementation, val = i - k * n stores $i-k_i\cdot n$, and best stores prefix minima after sorting by $P_i$. upper_bound locates the last position satisfying $P_i\le x$, and the answer is h * n + best[rem][idx]. If even the smallest prefix in the group is greater than $x$, there is no valid nonnegative number of laps.

A Negative Cycle Sum

Here, $S=-d$, so the equation becomes:

Therefore:

The validity condition is:

The number of steps can be written as:

We still sort each congruence class by $P_i$ in ascending order, but the valid candidates now form a suffix. Maintain suffix minima of:

For a query, use lower_bound to find the first prefix at least $x$, then retrieve the corresponding suffix minimum.

The adjustment here is val = i + k * n; best stores suffix minima, and the final answer is -h * n + best[rem][idx]. The positive and negative cases share the same congruence grouping; only the direction of the valid range and of the maintained minima changes.

If even the largest prefix in the group is less than $x$, the target is likewise unreachable.

Implementation Details and Boundaries

Taking the remainder of a negative number in C++ may produce a negative remainder. When grouping, always use:

to place remainders in $[0,d)$, so that negative prefixes and negative queries can enter the same group.

A prefix value may occur more than once; deduplication is unnecessary. The prefix or suffix minima automatically retain the candidate with the earlier step count.

For a query $x=0$, output $0$ directly. Even if the score returns to zero later, it cannot do so earlier than the initial state.

Prefix sums, queries, quotients, and expressions for step counts can all exceed the range of int, so use long long throughout.

Complexity

When $S=0$, building the hash table of earliest prefix positions takes $O(n)$ on average, and each query takes $O(1)$ on average.

When $S\ne 0$, sorting all the groups takes $O(n\log n)$ in total, and constructing the minima arrays takes another $O(n)$. Each query first finds its congruence class through a hash table, then binary-searches for the valid range within that group. The average total time complexity is therefore:

The space complexity is $O(n)$.

Accepted Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int maxn = 1e5 + 5;

int t;

ll mod(ll a, ll b) {
    return (a % b + b) % b;
}

void solve1(int m, unordered_map<ll, int> &f1st) {
    f1st[0] = 0;
    for (int i = 1; i <= m; i++) {
        ll x;
        cin >> x;
        if (f1st.count(x)) {
            cout << f1st[x] << '\n';
        } else {
            cout << -1 << '\n';
        }
    }
}

void solve2(int n, int m, ll s, vector<ll> &pre, unordered_map<ll, vector<pair<ll, ll> > > &same_rem) {
    for (int i = 0; i < n; i++) {
        ll rem = mod(pre[i], abs(s));
        ll k = (pre[i] - rem) / abs(s);
        ll val;
        if (s > 0) {
            val = i - k * n;
        } else {
            val = i + k * n;
        }
        same_rem[rem].push_back({pre[i], val});
    }
    unordered_map<ll, vector<ll> > best;
    for (auto &um: same_rem) {
        ll rem = um.first;
        sort(um.second.begin(), um.second.end());
        int size = um.second.size();
        best[rem] = vector<ll>(size);
        if (s > 0) {
            best[rem][0] = um.second[0].second;
            for (int i = 1; i < size; i++) {
                best[rem][i] = min(best[rem][i - 1], um.second[i].second);
            }
        } else {
            best[rem][size - 1] = um.second[size - 1].second;
            for (int i = size - 2; i >= 0; i--) {
                best[rem][i] = min(best[rem][i + 1], um.second[i].second);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        ll x;
        cin >> x;
        if (!x) {
            cout << 0 << '\n';
            continue;
        }
        ll d = abs(s);
        ll rem = mod(x, d);
        if (!same_rem.count(rem)) {
            cout << -1 << '\n';
            continue;
        }
        auto &v = same_rem[rem];
        if (s > 0) {
            int idx = upper_bound(v.begin(), v.end(), x, [](ll val, const auto &p) {
                return val < p.first;
            }) - v.begin() - 1;
            if (idx < 0) {
                cout << -1 << '\n';
                continue;
            }
            ll h = (x - rem) / s;
            cout << h * n + best[rem][idx] << '\n';
        } else {
            int idx = lower_bound(v.begin(), v.end(), x, [](const auto &p, ll val) {
                return p.first < val;
            }) - v.begin();
            if (idx == (int) v.size()) {
                cout << -1 << '\n';
                continue;
            }
            ll h = (x - rem) / d;
            cout << -h * n + best[rem][idx] << '\n';
        }
    }
}

void op() {
    int n, m;
    cin >> n >> m;
    ll s = 0;
    vector<int> a(n + 5);
    vector<ll> pre(n + 5, 0);
    unordered_map<ll, int> f1st;
    unordered_map<ll, vector<pair<ll, ll> > > same_rem;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s += a[i];
        if (!f1st.count(s)) {
            f1st[s] = i;
        }
        if (i != n) {
            pre[i] = s;
        }
    }
    if (!s) {
        solve1(m, f1st);
    } else {
        pre[0] = 0;
        solve2(n, m, s, pre, same_rem);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    while (t--) {
        op();
    }
    return 0;
}