Overview

This is a game where a ball is passed by counting only the children remaining in the circle, and the previous holder leaves immediately after passing. We solve this by efficiently managing “what position a child is among the remaining children.”

Analysis

At each pass, starting from the child next to the current ball holder \(x\), we count only the children remaining in the circle.

Naively advancing \(D_i\) people at a time won’t work in time, since \(D_i\) can be up to \(10^9\). Also, managing the circle with an array or list and advancing step by step each time results in \(O(NM)\) in the worst case.

The key observations are:

• The order of the circle is fixed as \(1, 2, \ldots, N\)
• Children only leave (they are never added)
• What we need is the information “what position is this child among the remaining children”

So, we manage each child as \(1\) if they are still in the circle, and \(0\) if they have left.

Let \(\mathrm{alive}\) be the current number of remaining people. Since we don’t count the current child \(x\) themselves, the number of people to count among is \(\mathrm{alive} - 1\).

Therefore, the \(D_i\)-th child counted is effectively the same as the

\[ k = (D_i - 1) \bmod (\mathrm{alive} - 1) + 1 \]

-th child.

For example, if there are \(5\) remaining people and we count among the \(4\) others, \(D_i = 1, 5, 9, \ldots\) all refer to the same child.

Next, suppose the current child \(x\) is the \(r\)-th among the remaining children. Then, the child \(k\) positions ahead in the clockwise direction is the

\[ ((r + k - 1) \bmod \mathrm{alive}) + 1 \]

-th among all remaining children.

To efficiently find “the number of the \(t\)-th child among the remaining children,” we use a Fenwick Tree.

Algorithm

The Fenwick Tree stores the following value for each child:

• \(1\) if the child is still in the circle
• \(0\) if the child has already left

Using a Fenwick Tree, the following operations can be performed efficiently:

• sum(x) Find the number of remaining children from number \(1\) to \(x\). In other words, determine what position child \(x\) is among the remaining children.

• kth(k) Find the number of the \(k\)-th child among the remaining children.

The procedure is as follows:

1. Initially, all children are present, so set all positions in the Fenwick Tree to \(1\).

2. Set the current ball holder to current = S.

3. For each pass, do the following:

   1. Let alive be the current number of remaining people.
   2. Compute the effective number of positions to advance:

   $\( k = (D_i - 1) \bmod (\mathrm{alive} - 1) + 1 \)$

   1. Find the rank of the current child:

   $\( r = \mathrm{sum}(\mathrm{current}) \)$

   1. Compute the rank of the next child to receive the ball:

   $\( \mathrm{next\_rank} = ((r + k - 1) \bmod \mathrm{alive}) + 1 \)$

   1. Find the actual child number next using kth(next_rank).
   2. Remove the current child from the Fenwick Tree.
   3. Set current = next and decrease the remaining count by \(1\).

4. Finally, output current.

Complexity

• Time complexity: \(O((N+M)\log N)\)
• Space complexity: \(O(N)\)

Implementation Notes

The kth(k) function of the Fenwick Tree finds “the first position where the prefix sum becomes at least \(k\)” using a binary search-like approach. This allows us to find the number of the \(k\)-th remaining child in \(O(\log N)\).

Also, since \(D_i\) can be as large as \(10^9\), it is safe to use long long for computations.

At the time of each pass, the current child current is still present in the Fenwick Tree. Note that we first determine the next recipient in this state, and only then remove current.

Source Code

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<int> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    int sum(int idx) const {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }

    int kth(int k) const {
        int idx = 0;
        int step = 1;
        while ((step << 1) <= n) step <<= 1;

        for (; step > 0; step >>= 1) {
            int nxt = idx + step;
            if (nxt <= n && bit[nxt] < k) {
                idx = nxt;
                k -= bit[nxt];
            }
        }
        return idx + 1;
    }
};

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

    int N, M, S;
    cin >> N >> M >> S;

    Fenwick fw(N);
    for (int i = 1; i <= N; i++) fw.add(i, 1);

    int current = S;
    int alive = N;

    for (int i = 0; i < M; i++) {
        long long D;
        cin >> D;

        long long k = (D - 1) % (alive - 1) + 1;
        int rank_current = fw.sum(current);

        int next_rank = (int)(((long long)rank_current + k - 1) % alive + 1);
        int next = fw.kth(next_rank);

        fw.add(current, -1);
        current = next;
        alive--;
    }

    cout << current << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-xhigh.