ยิงธนู: เลิกจำลองกระดาน แล้วเปลี่ยนสนามทั้งสนามให้เป็นค่าน้อยสุดของช่วง

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

int main() {
    long long N, R;
    scanf("%lld %lld", &N, &R);
    vector<int> s(2 * N);
    for (int i = 0; i < 2 * N; i++) scanf("%d", &s[i]);
    int me = s[0];
    vector<int> o(s.begin() + 1, s.end());     // คนอื่น 2N-1 คน เรียงจากซ้ายไปขวา

    // หลัง 2N รอบระบบวนคาบ N ส่วนที่เกินจึงตัดทิ้งได้ เดินจริงไม่เกิน 4N รอบ
    long long T = (R <= 3 * N) ? R : 3 * N + ((R - 3 * N) % N);

    vector<int> c(N + 2), nc(N + 2);
    long long bestFinal = LLONG_MAX, bestStart = -1;

    for (long long k = 1; k <= N; k++) {
        // แทรกตัวเองที่เป้า k แล้วคนอื่นจับคู่กันตามลำดับเดิม
        for (long long i = 1; i <= N; i++) {
            int a, b;
            if (i < k)       { a = o[2 * i - 2]; b = o[2 * i - 1]; }
            else if (i == k) { a = o[2 * i - 2]; b = me; }
            else             { a = o[2 * i - 3]; b = o[2 * i - 2]; }
            c[i] = (a <= me) + (b <= me);      // นับคนที่เราไม่ชนะ (รวมตัวเราเอง)
        }

        long long pos = k;
        for (long long q = 0; q < T; q++) {
            // เราคือคนที่อ่อนที่สุดในกลุ่ม "ไม่แพ้ให้เรา" คู่แข่งจึงแข็งกว่าเรา
            // ก็ต่อเมื่อช่องนี้มีคนกลุ่มนั้นอยู่สองคน คือเรากับอีกคนหนึ่ง
            bool oppStrong = (c[pos] == 2);
            if (pos == 1) pos = oppStrong ? N : 1;   // แพ้ที่เป้า 1 คือถูกส่งไปท้ายแถว
            else if (!oppStrong) pos--;              // ชนะที่เป้าอื่นคือขยับไปทางซ้าย

            for (long long i = 1; i <= N; i++) {
                if (i == 1)      nc[1] = (c[1] >= 1) + (N >= 2 ? (c[2] >= 1) : 0);
                else if (i < N)  nc[i] = (c[i] == 2) + (c[i + 1] >= 1);
                else             nc[N] = (c[N] == 2) + (c[1] == 2);
            }
            if (N == 1) nc[1] = c[1];
            swap(c, nc);
        }

        if (pos < bestFinal) { bestFinal = pos; bestStart = k; }
        else if (pos == bestFinal) bestStart = k;    // เสมอกันเลือกเป้าเริ่มต้นที่มากที่สุด
    }

    printf("%lld\n", bestStart);
    return 0;
}

// ตัวตรวจสอบแบบซื่อ ๆ จำลองคนจริงทุกคนครบ R รอบ ใช้ได้แค่ N เล็ก ๆ กับ R ไม่กี่ร้อย
// เอาไว้สุ่มเทียบกับโค้ดจริงก่อนส่ง ไม่ใช่โค้ดที่ส่งเข้าระบบตัดสิน
#include <bits/stdc++.h>
using namespace std;

int N; long long R;
int me;
vector<int> o;

int simulate(int k, long long rounds) {
    vector<int> line;
    for (int i = 0; i < 2 * k - 2; i++) line.push_back(o[i]);
    line.push_back(me);
    for (int i = 2 * k - 2; i < (int)o.size(); i++) line.push_back(o[i]);

    vector<array<int, 2>> t(N + 1);
    for (int i = 1; i <= N; i++) { t[i][0] = line[2 * i - 2]; t[i][1] = line[2 * i - 1]; }

    for (long long q = 0; q < rounds; q++) {
        vector<int> win(N + 1), los(N + 1);
        for (int i = 1; i <= N; i++) {
            win[i] = min(t[i][0], t[i][1]);       // เลขลำดับน้อยกว่าคือเก่งกว่า
            los[i] = max(t[i][0], t[i][1]);
        }
        vector<array<int, 2>> nt(N + 1);
        for (int i = 1; i <= N; i++) {
            if (i == 1)      nt[i] = {win[1], N >= 2 ? win[2] : los[1]};
            else if (i < N)  nt[i] = {los[i], win[i + 1]};
            else             nt[i] = {los[N], los[1]};
        }
        if (N == 1) nt[1] = t[1];
        t = nt;
    }
    for (int i = 1; i <= N; i++) if (t[i][0] == me || t[i][1] == me) return i;
    return -1;
}

int main() {
    scanf("%d %lld", &N, &R);
    scanf("%d", &me);
    o.resize(2 * N - 1);
    for (int i = 0; i < 2 * N - 1; i++) scanf("%d", &o[i]);

    int best = INT_MAX, bestK = -1;
    for (int k = 1; k <= N; k++) {
        int f = simulate(k, R);
        if (f < best) { best = f; bestK = k; }
        else if (f == best) bestK = k;
    }
    printf("%d\n", bestK);
}

// Archery (IOI 2009) เฉลยเต็มขอบเขต N <= 200,000
//
// แนวคิดสามชั้น
//   1) ย่อโลก: คนอื่นสำคัญแค่ "แข็งกว่าเรา" หรือไม่  นับเป็นโทเคนต่อเป้า n[i] in {0,1,2}
//   2) แทนที่จะจำลองกระดานทุกรอบ ให้คิดเป็น "การไหล" F_i(t) = จำนวนโทเคนที่ออกจากเป้า i ครบ t รอบ
//      ซึ่งมีสูตรปิดแบบ min-plus:  F_i(t) = min over j ของ (t - j) + (ผลรวม n ของเป้า i..i+j-1)
//      สูตรนี้ยุบเหลือการถามค่าน้อยสุดของช่วงบนอาเรย์เดียว ตอบได้ในเวลาคงที่
//   3) เป้า 1 มีกติกากลับด้าน (ผู้ชนะอยู่ต่อ) สูตรจึงใช้ได้ต่อเมื่อเป้า 1 มีโทเคนแล้ว
//      ก่อนหน้านั้นเป็นช่วงตั้งตัวที่ไม่มีใครวนกลับ คิดแยกเป็นเฟสแรก
// สุดท้าย u(k) = k - (จำนวนก้าวซ้าย) เป็นฟังก์ชันไม่ลด จึงค้นหาคำตอบแบบไบนารีได้
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N;
ll R, T;
int me;
vector<int> b;                 // b[j] = 1 ถ้าคนที่ j ในแถว (ไม่รวมเรา) แข็งกว่าเรา

// ---- บัฟเฟอร์ใช้ซ้ำทุกครั้งที่ประเมิน u(k) ----
vector<int> n0, nt1;
vector<int> P1, G1, P2, G2;
vector<ll> f1at;               // F1(i, t1) ของทุกเป้า

static inline int stationOf(ll y) {          // y เป็นดัชนีที่คลี่วงออกแล้ว
    ll r = y % N; if (r <= 0) r += N; return (int)r;
}

/** คืน u(k) = k - จำนวนก้าวซ้ายทั้งหมด และถ้า outPos ไม่เป็น null ก็คืนเป้าสุดท้ายด้วย */
ll evalU(int k, int* outPos) {
    for (int i = 1; i <= N; i++) {
        if (i < k)       n0[i] = b[2 * i - 2] + b[2 * i - 1];
        else if (i == k) n0[i] = b[2 * k - 2];
        else             n0[i] = b[2 * i - 3] + b[2 * i - 2];
    }
    int i0 = 0;
    for (int i = 1; i <= N; i++) if (n0[i] >= 1) { i0 = i; break; }
    ll t1 = (n0[1] >= 1) ? 0 : i0 - 1;       // เฟสแรกจบตอนโทเคนตัวแรกถึงเป้า 1

    // ---------- เฟส 1 : เป้า 1 ยังไม่ปล่อยใคร เส้นทาง min-plus จึงจบที่เป้า 1 ----------
    ll L1 = 2LL * N + 4;
    P1.assign(L1 + 2, 0);
    for (ll y = 2; y <= L1 + 1; y++) P1[y] = P1[y - 1] + ((y - 1 <= N) ? n0[y - 1] : 0);
    G1.assign(L1 + 2, 0);
    for (ll y = 0; y <= L1 + 1; y++) G1[y] = P1[y] - (int)y;

    ll pos = k, steps = 0;
    // เฟสแรกยาวไม่เกิน N รอบ และเราไม่มีทางวนข้ามเป้า 1 ในเฟสนี้ จึงเดินตรง ๆ ได้
    {
        ll winL = k, winR = k;               // หน้าต่างของ F1(pos, t)
        ll mnCur = G1[k];
        ll sL = k + 1, sR = k + 1;           // หน้าต่างของ F1(pos+1, t)
        ll mnSrc = G1[min(sL, L1)];
        for (ll t = 0; t < min(t1, T); t++) {
            ll fp = (pos == 1) ? 0 : (t - P1[pos] + pos + mnCur);
            ll src = pos + 1;
            ll fs = (stationOf(src) == 1) ? 0 : (t - P1[src] + src + mnSrc);
            bool blocked = (n0[pos] + fs - fp) >= 1;
            bool moved = (pos == 1) ? blocked : !blocked;
            if (moved) { pos--; steps++; }   // ในเฟสแรกเป้า 1 ไม่มีโทเคน เราจึงไม่มีทางถูกเตะ
            // ขยายหน้าต่างทั้งสอง (ขยายอย่างเดียว ไม่เคยหด)
            ll nwL = pos, nwR = pos + (t + 1);
            while (winL > nwL) { winL--; mnCur = min<ll>(mnCur, G1[winL]); }
            while (winR < nwR) { winR++; if (winR <= L1) mnCur = min<ll>(mnCur, G1[winR]); }
            ll nsL = pos + 1, nsR = pos + 1 + (t + 1);
            while (sL > nsL) { sL--; mnSrc = min<ll>(mnSrc, G1[sL]); }
            while (sR < nsR) { sR++; if (sR <= L1) mnSrc = min<ll>(mnSrc, G1[sR]); }
        }
    }

    if (T <= t1) { if (outPos) *outPos = (int)pos; return k - steps; }

    // ---------- สภาพกระดานตอนจบเฟสแรก ----------
    // F1(i, t1) ของทุกเป้า หาได้ด้วยหน้าต่างเลื่อนความกว้างคงที่
    f1at.assign(N + 3, 0);
    {
        deque<ll> dq;
        ll hi0 = min<ll>(1 + t1, L1);
        for (ll x = 1; x <= hi0; x++) { while (!dq.empty() && G1[dq.back()] >= G1[x]) dq.pop_back(); dq.push_back(x); }
        for (ll i = 1; i <= N + 1; i++) {
            ll hi = min(i + t1, L1);
            while (!dq.empty() && dq.front() < i) dq.pop_front();
            while (!dq.empty() && dq.back() > hi) dq.pop_back();
            for (ll x = max(i, hi0 + 1); x <= hi; x++) { while (!dq.empty() && G1[dq.back()] >= G1[x]) dq.pop_back(); dq.push_back(x); }
            hi0 = max(hi0, hi);
            f1at[i] = (stationOf(i) == 1) ? 0 : (t1 - P1[i] + i + G1[dq.front()]);
        }
    }
    nt1.assign(N + 2, 0);
    for (int i = 1; i <= N; i++) {
        int src = (i < N) ? i + 1 : 1;
        ll fs = (src == 1) ? 0 : f1at[src];
        nt1[i] = (int)(n0[i] + fs - f1at[i]);
    }

    // ---------- เฟส 2 : เป้า 1 มีโทเคนแล้ว สูตร min-plus แบบวนใช้ได้ทั้งหมด ----------
    ll OFF = T + 5;                          // เลื่อนดัชนีให้ไม่ติดลบ
    ll L2 = OFF + N + T + 5;
    P2.assign(L2 + 2, 0);
    for (ll y = 1; y <= L2 + 1; y++) {
        int s = stationOf(y - 1 - OFF);
        P2[y] = P2[y - 1] + nt1[s] - (s == 1 ? 1 : 0);
    }
    G2.assign(L2 + 2, 0);
    for (ll y = 0; y <= L2 + 1; y++) G2[y] = P2[y] - (int)y;

    ll y = pos + OFF;                        // ดัชนีที่คลี่แล้วของตำแหน่งเรา
    ll wL = y, wR = y, mnCur = G2[y];
    ll sL = y + 1, sR = y + 1, mnSrc = G2[y + 1];
    for (ll t = 0; t < T - t1; t++) {
        ll fp = t - P2[wL] + wL + mnCur;
        ll fs = t - P2[sL] + sL + mnSrc;
        int st = stationOf(y - OFF);
        bool blocked = ((ll)nt1[st] + fs - fp) >= 1;
        bool moved = (st == 1) ? blocked : !blocked;
        if (moved) { y--; steps++; }
        ll nwL = y, nwR = y + (t + 1);
        while (wL > nwL) { wL--; mnCur = min<ll>(mnCur, G2[wL]); }
        while (wR < nwR) { wR++; mnCur = min<ll>(mnCur, G2[wR]); }
        ll nsL = y + 1, nsR = y + 1 + (t + 1);
        while (sL > nsL) { sL--; mnSrc = min<ll>(mnSrc, G2[sL]); }
        while (sR < nsR) { sR++; mnSrc = min<ll>(mnSrc, G2[sR]); }
    }
    if (outPos) *outPos = stationOf(y - OFF);
    return k - steps;
}

int main() {
    scanf("%d %lld", &N, &R);
    vector<int> s(2 * N);
    for (int i = 0; i < 2 * N; i++) scanf("%d", &s[i]);
    me = s[0];
    if (me == 1) { printf("%d\n", N); return 0; }   // เก่งที่สุด อยู่เป้า 1 แน่นอน จึงเลือกเป้าเริ่มมากสุด

    b.assign(2 * N - 1, 0);
    for (int i = 1; i < 2 * N; i++) b[i - 1] = (s[i] < me) ? 1 : 0;
    T = (R <= 2LL * N) ? R : 2LL * N + ((R - 2LL * N) % N);

    n0.assign(N + 2, 0);
    auto U = [&](int k) { return evalU(k, nullptr); };

    ll u1 = U(1), uN = U(N);
    auto fOf = [&](ll u) { ll r = (u - 1) % N; if (r < 0) r += N; return r + 1; };

    // k ที่ใหญ่ที่สุดที่ u(k) <= v  (u ไม่ลด จึงค้นหาแบบไบนารีได้)
    auto lastLE = [&](ll v) {
        int lo = 1, hi = N, res = 1;
        while (lo <= hi) { int md = (lo + hi) / 2; if (U(md) <= v) { res = md; lo = md + 1; } else hi = md - 1; }
        return res;
    };
    // k ที่เล็กที่สุดที่ u(k) >= v
    auto firstGE = [&](ll v) {
        int lo = 1, hi = N, res = -1;
        while (lo <= hi) { int md = (lo + hi) / 2; if (U(md) >= v) { res = md; hi = md - 1; } else lo = md + 1; }
        return res;
    };

    auto fdiv = [&](ll a, ll m) { ll d = a / m; if ((a % m) && ((a < 0) != (m < 0))) d--; return d; };

    // u ไม่ลด แต่ช่วงของมันกว้างได้เกิน N จึงข้ามเส้นแบ่งบล็อกได้หลายครั้ง
    // ผู้เข้าชิงคือค่า u ที่เล็กที่สุดของแต่ละบล็อก เพราะภายในบล็อกเดียวกัน f เพิ่มตาม u
    vector<ll> cand;
    cand.push_back(u1);
    for (ll v = (ll)N * (fdiv(u1 - 1, N) + 1) + 1; v <= uN; v += N) {
        int kw = firstGE(v);
        if (kw > 0) cand.push_back(U(kw));
    }
    ll bestF = LLONG_MAX, bestU = 0;
    for (ll u : cand) {
        ll f = fOf(u);
        if (f < bestF || (f == bestF && u > bestU)) { bestF = f; bestU = u; }
    }
    int ans = lastLE(bestU);
    printf("%d\n", ans);
    return 0;
}

// ผู้เข้าชิงคือค่า u ที่เล็กที่สุดของแต่ละบล็อก สองบล็อกให้เป้าสุดท้ายเท่ากันได้
ll bestF = LLONG_MAX, bestU = 0;
for (ll u : cand) {
    ll f = fOf(u);
    if (f < bestF) { bestF = f; bestU = u; }   // บรรทัดที่ผิด เสมอกันแล้วเก็บตัวที่เจอก่อน
}
int ans = lastLE(bestU);                       // ค่า u ที่เจอก่อนคือค่าน้อยกว่า จุดเริ่มจึงเล็กเกิน

2 4
3
1
4
2