Overview

This is a problem where “among survivors arranged in a circle, each time you must quickly find the \(D_i\)-th person from the current position, then remove the current child.” The key point is efficiently handling order statistics with deletions (finding the \(k\)-th element).

Analysis

If we simulate this problem directly, for each pass we need to “count the next survivors in order.”
However, since \(N \le 2\times 10^5\), searching linearly each time results in \(O(NM)\) in the worst case, which is too slow.

Key Observation 1: The counting target is “survivors excluding the current child \(x\)”

At the start of the \(i\)-th pass, if we let the number of survivors be alive = N - i, then the number of candidates is
\(\text{others} = \text{alive} - 1\)
(since \(x\) is excluded).

Since \(D_i\) can be very large (up to \(10^9\)), there’s no need to count that many directly. By computing $\( k = (D_i - 1) \bmod \text{others} + 1 \)\( we can compress it to "the actual needed \)1$-st through others-th position.”

Key Observation 2: “Counting from the next after \(x\)” in the circle can be split into two intervals

Looking at the number order (1..N), clockwise from the next after \(x\) gives:

1. Interval \([x+1, N]\)
2. Followed by interval \([1, x-1]\)

(of course, skipping already removed elements).
Therefore: - First, count the number of survivors in \([x+1, N]\): cntAfterX - If \(k \le cntAfterX\), find the \(k\)-th element within that interval - Otherwise, take the \((k - cntAfterX)\)-th element from the front side (the overall front including \([1, x-1]\))

How to Speed This Up

The required operations are the following three:

• Update (delete) the alive flag at position \(i\) by \(+1/-1\)
• Get the number of survivors in a given interval (prefix sum)
• Get “the \(r\)-th numbered person” among survivors (order statistics)

This can be achieved with a Fenwick Tree (BIT).
By storing “1 if alive, 0 if eliminated” at each position, all the above operations are possible in \(O(\log N)\).

Algorithm

1. Create a Fenwick Tree of size \(N\), initially inserting 1 at every position since everyone is alive.
2. Set the current ball holder x = S.
3. For each pass \(i=0..M-1\):
   • alive = N - i
   • others = alive - 1
   • \(k = (D_i - 1)\bmod others + 1\)
   • Get cntAfterX = sum(x+1..N)
   • Determine the next receiver target:
     • When k <= cntAfterX:
       rank = sum(1..x) + k (sequential rank among survivors)
       target = kth(rank)
     • Otherwise:
       rem = k - cntAfterX
target = kth(rem)
   • Eliminate the current x (add(x, -1))
   • Update x = target
4. Output the final x.

kth(r) uses “binary search on the Fenwick tree” to return the smallest index where the cumulative sum of survivors first reaches \(r\) or more.

Complexity

• Time complexity: \(O((N+M)\log N)\)
  (\(N\) initial updates + a constant number of Fenwick operations per pass)
• Space complexity: \(O(N)\)

Implementation Notes

• Since \(D_i\) can be large, read it as long long (after the modulo computation, int is fine).

• others is always at least 1 (since \(M \le N-1\)), so division by zero never occurs.

• Implementing the Fenwick tree as 1-indexed makes kth easier to write.

• In this code, “the receiver is determined first, then the current x is removed,” which matches the problem’s procedure (leaving immediately after passing).

  Source Code

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

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n = 0) { init(n); }
    void init(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }
    void add(int i, int v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    int sumPrefix(int i) const {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
    int sumRange(int l, int r) const {
        if (l > r) return 0;
        return sumPrefix(r) - sumPrefix(l - 1);
    }
    int kth(int k) const { // 1-indexed k
        int idx = 0;
        int pw = 1;
        while ((pw << 1) <= n) pw <<= 1;
        for (int d = pw; d > 0; d >>= 1) {
            int nxt = idx + d;
            if (nxt <= n && bit[nxt] < k) {
                k -= bit[nxt];
                idx = nxt;
            }
        }
        return idx + 1;
    }
};

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

    int N, M, S;
    cin >> N >> M >> S;
    vector<long long> D(M);
    for (int i = 0; i < M; i++) cin >> D[i];

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

    int x = S;

    for (int i = 0; i < M; i++) {
        int alive = N - i;          // before removing x
        int others = alive - 1;     // candidates excluding x

        long long k = (D[i] - 1) % others + 1; // 1..others

        int cntAfterX = fw.sumRange(x + 1, N);
        int target;
        if (k <= cntAfterX) {
            int rank = fw.sumPrefix(x) + (int)k;
            target = fw.kth(rank);
        } else {
            int rem = (int)(k - cntAfterX);
            target = fw.kth(rem);
        }

        fw.add(x, -1); // x leaves
        x = target;    // ball holder for next pass
    }

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

---

This editorial was generated by gpt-5.3-codex.