Overview

This is a simulation problem where \(N\) children standing in a circle pass a ball, and the child who passes the ball leaves the circle. Since the number of passes \(M\) and the movement distances \(D_i\) can be large, a naive simulation is insufficient, and optimization using data structures is required.

Analysis

Limitations of Naive Simulation

If we directly implement the operation of “finding and removing the \(D_i\)-th person” using a list or linked list, each pass takes \(O(N)\) time in the worst case. Since passes are performed \(M\) times (up to \(N-1\) times), the overall time complexity becomes \(O(NM)\), which will not meet the time limit under the constraints \(N, M \le 2 \times 10^5\). Additionally, since \(D_i\) can be as large as \(10^9\), it is impossible to naively count one person at a time.

Strategy for Optimization

The operations required in this problem are the following two: 1. Quickly determine “who is the \(k\)-th person among the children currently remaining in the circle.” 2. Quickly update the information that “a child has left the circle.”

To perform these efficiently, we utilize a Fenwick Tree (Binary Indexed Tree, BIT).

Management by Rank

We manage the BIT by assigning \(1\) to children remaining in the circle and \(0\) to those who have left. - The rank (position) of a child \(i\) among the currently remaining children can be obtained by computing the prefix sum query(i) from \(1\) to \(i\) in the BIT. - Conversely, to determine the child number \(i\) from the current rank \(k\), we can perform a binary search (or binary lifting) on the BIT in \(O(\log N)\).

Movement Calculation

Let \(r\) be the rank of the current ball holder, and \(K\) be the number of remaining people. When counting the \(D_i\)-th person among the \(K-1\) people excluding the ball holder, the actual number of steps to move can be simplified as \(step = (D_i - 1) \pmod{K-1} + 1\). - When moving \(step\) positions clockwise from the current rank \(r\): - If \(r + step \le K\), the rank of the next holder is \(r + step\). - If \(r + step > K\), the ball wraps around the circle, so the rank becomes \(step - (K - r)\).

Algorithm

1. Initialization: Create a BIT of length \(N\) and set all elements to \(1\).
2. Pass Simulation: For each of the \(M\) passes, do the following:
   • Determine the current number of people \(K\) (\(K = N - (\text{number of people who have left so far})\)).
   • Obtain the rank \(r\) of the current holder current_holder from the BIT.
   • Calculate the rank target_rank of the child who will receive the ball next, using the remainder of \(D_i\) divided by \(K-1\).
   • Determine the child number next_holder of the target_rank-th child using binary search on the BIT.
   • Remove current_holder from the circle (update the value at position current_holder in the BIT to \(0\)).
   • Update the holder to next_holder.
3. Output: Output the final current_holder.

Complexity

• Time Complexity: \(O(M \log N)\)
  • BIT update and query take \(O(\log N)\).
  • find_kth (binary search on BIT) takes \(O(\log N)\).
  • Since this is repeated \(M\) times, the overall complexity is \(O(M \log N)\), which is sufficiently fast.
• Space Complexity: \(O(N)\)
  • The array for managing the BIT uses \(O(N)\) memory.

Implementation Notes

• Binary Search on BIT: In the find_kth function, using a standard binary search (lower_bound) results in \(O(\log^2 N)\), but by utilizing the structure of the BIT with Binary Lifting, it can be implemented in \(O(\log N)\).

• Handling Large \(D_i\): Since \(D_i\) can be very large, it must be received as a long long type, and the remainder must be taken with the current effective number of people \(K-1\).

• 1-based Indexing: Since BIT is typically managed starting from index 1, it can be directly mapped to child numbers \(1 \dots N\), making the implementation straightforward.

  Source Code

#include <iostream>
#include <vector>

using namespace std;

/**
 * FenwickTree (Binary Indexed Tree)
 * 競技プログラミングにおいて、要素の更新と累積和の取得をそれぞれ O(log N) で行うデータ構造です。
 * ここでは円陣に残っている子供の人数を管理するために使用します。
 */
template <typename T>
struct FenwickTree {
    int n;
    vector<T> tree;

    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    // i番目の要素にxを加算する
    void add(int i, T x) {
        for (; i <= n; i += i & -i) {
            tree[i] += x;
        }
    }

    // 1番目からi番目までの要素の合計を返す
    T query(int i) {
        T res = 0;
        for (; i > 0; i -= i & -i) {
            res += tree[i];
        }
        return res;
    }

    // 累積和がk以上となる最小のインデックスを O(log N) で見つける
    // これにより「現在残っている子供の中でk番目の子供」を高速に特定できます
    int find_kth(T k) {
        int idx = 0;
        int max_pow = 1;
        while (max_pow * 2 <= n) max_pow *= 2;
        for (int i = max_pow; i > 0; i >>= 1) {
            if (idx + i <= n && tree[idx + i] < k) {
                idx += i;
                k -= tree[idx];
            }
        }
        return idx + 1;
    }
};

int main() {
    // 入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, S;
    if (!(cin >> N >> M >> S)) return 0;

    // 最初はすべての子供（1からN）が円陣にいます
    FenwickTree<int> ft(N);
    for (int i = 1; i <= N; ++i) {
        ft.add(i, 1);
    }

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

        // 現在円陣に残っている子供の総数
        int K = N - i;
        
        // 現在ボールを持っている子供の、残っている子供たちの中での順番（ランク）
        int r = ft.query(current_holder);
        
        // ボールを持っている子供を除いた残りの子供の数は K-1
        // その中を時計回りに D 番目数える操作は、(D-1) % (K-1) + 1 番目と同じ
        long long step = (D - 1) % (K - 1) + 1;
        
        int target_rank;
        // 現在のランク r から時計回りに step 進んだときのランクを計算
        if ((long long)r + step <= (long long)K) {
            // 円の末尾（番号N）を超えない場合
            target_rank = (int)((long long)r + step);
        } else {
            // 円を一周して戻る場合
            target_rank = (int)(step - (long long)(K - r));
        }

        // 次にボールを受け取る子供の番号を特定
        int next_holder = ft.find_kth(target_rank);
        
        // ボールを渡した直後、元の持ち主は円陣から抜ける
        ft.add(current_holder, -1);
        
        // ボールが渡される
        current_holder = next_holder;
    }

    // M回のパス終了後にボールを持っている子供の番号を出力
    cout << current_holder << endl;

    return 0;
}

---

This editorial was generated by gemini-3-flash-thinking.