Archery

Solution

Binary Search on Starting Position

The key observation is that your final position after $R$ rounds is a function of your starting target, and this function has structure that allows binary search (or a direct $O(N \log N)$ approach).

After at most $N$ rounds, the configuration becomes periodic. So we simulate $\min(R, 2N)$ rounds. For each candidate starting position, the simulation runs in $O(N)$ time.

Efficient Simulation

For a fixed starting target $p$:

1. Place yourself at target $p$; distribute the other $2N$ archers into the targets.

2. Simulate $\min(R, 2N)$ rounds, tracking your position.

3. The simulation can be optimized by noting that after entering target 1, you either stay there (if you keep winning) or get pushed to target 2.

Complexity

• Binary search + simulation: $O(N^2)$ in the worst case (trying $O(N)$ starting positions with $O(N)$ simulation each), or $O(N \log N)$ with binary search on the starting position.

• Space: $O(N)$.

C++ Solution

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

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

    int N, R;
    cin >> N >> R;

    // Read 2N archer strengths (lower rank = stronger)
    // Archers are 0-indexed; we are archer 2N (id = 2*N)
    int myRank;
    cin >> myRank;

    vector<int> strength(2 * N);
    for(int i = 0; i < 2 * N; i++) cin >> strength[i];

    int R_eff = min(R, 2 * N);
    int me = 2 * N;

    // Compare strengths: lower rank = stronger
    auto stronger = [&](int a, int b) -> bool {
        int sa = (a == me) ? myRank : strength[a];
        int sb = (b == me) ? myRank : strength[b];
        return sa < sb;
    };

    auto simulate = [&](int startPos) -> int {
        // Place archers: 2 per target, we replace one at startPos
        vector<array<int,2>> targets(N);
        int idx = 0;
        for(int t = 0; t < N; t++){
            if(t == startPos){
                targets[t] = {me, idx};
                idx++;
            } else {
                targets[t] = {idx, idx + 1};
                idx += 2;
            }
        }

        int myTarget = startPos;
        for(int r = 0; r < R_eff; r++){
            vector<vector<int>> newTargets(N);
            for(int t = 0; t < N; t++){
                int a = targets[t][0], b = targets[t][1];
                int winner, loser;
                if(stronger(a, b)){ winner = a; loser = b; }
                else { winner = b; loser = a; }
                newTargets[max(0, t - 1)].push_back(winner);
                newTargets[min(N - 1, t + 1)].push_back(loser);
            }
            for(int t = 0; t < N; t++){
                targets[t] = {newTargets[t][0], newTargets[t][1]};
                for(int x : newTargets[t])
                    if(x == me) myTarget = t;
            }
        }
        return myTarget;
    };

    int bestTarget = N, bestStart = 0;
    for(int p = 0; p < N; p++){
        int result = simulate(p);
        if(result < bestTarget){
            bestTarget = result;
            bestStart = p;
        }
    }

    cout << bestStart + 1 << "\n";
    return 0;
}

Notes

The solution above is a direct simulation, correct for small inputs. For the full IOI constraints ($N$ up to $200\,000$), the intended $O(N \log N)$ solution exploits the following: binary search on the starting position combined with an efficient check that uses the observation that after entering target 1, the archer's subsequent behavior is periodic and predictable. The binary search works because the function mapping starting position to final position is structured (piecewise monotone).