#1168770 (C++23) No.3627 Share the Median

• 問題: No.3627 Share the Median
• ユーザー: 👑 loop0919
• 提出日時: 2026-06-10 01:07:24
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: WA
  (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 4,849 bytes
• コンパイル時間: 2,134 ms
• コンパイル使用メモリ: 351,712 KB
• 実行使用メモリ: 9,544 KB
• 平均クエリ数: 1.00
• 最終ジャッジ日時: 2026-08-14 20:51:01
• 合計ジャッジ時間: 5,666 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

サブタスク	配点	結果
Sample	0 %
Easy	20 %	WA * 16
Hard	80 %	WA * 24
合計	3 * 0% = 0 点

ソースコード

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

using ll = long long;

const ll INF = (1LL << 62);

struct Item {
    ll val;
    int idx; // original 1-indexed index
};

struct Solver {
    bool isAlice;
    int N, M;
    vector<Item> S;

    int da = 0, db = 0; // discarded count from A / B
    int k_rank = 0;

    int lenA() const {
        return N - da;
    }

    int lenB() const {
        return M - db;
    }

    int myLen() const {
        return isAlice ? lenA() : lenB();
    }

    int myOffset() const {
        return isAlice ? da : db;
    }

    int dummyIndex() const {
        return S[0].idx;
    }

    ll shareIndex(int idx) {
        cout << "share " << idx << '\n';
        cout.flush();

        ll v;
        if (!(cin >> v)) exit(0);
        if (v == -1) exit(0);
        return v;
    }

    void answerAndContinue(ll ans) {
        cout << "answer " << ans << '\n';
        cout.flush();

        int r;
        if (!(cin >> r)) exit(0);
        if (r == -1) exit(0);
    }

    // rank-th value/index in my remaining sequence.
    // rank is 1-indexed.
    pair<int, ll> myRankInfo(int rank) const {
        int len = myLen();
        int off = myOffset();

        if (1 <= rank && rank <= len) {
            const Item &it = S[off + rank - 1];
            return {it.idx, it.val};
        } else {
            return {dummyIndex(), INF};
        }
    }

    // One communication round.
    //
    // Alice sends rankA-th remaining A value.
    // Bob sends rankB-th remaining B value.
    //
    // If that rank does not exist, that player sends a dummy index,
    // and both players logically treat the value as INF.
    pair<ll, ll> exchangeRanks(int rankA, int rankB) {
        bool validA = (1 <= rankA && rankA <= lenA());
        bool validB = (1 <= rankB && rankB <= lenB());

        if (isAlice) {
            auto [idx, myVal] = myRankInfo(rankA);
            ll recv = shareIndex(idx);

            ll aVal = validA ? myVal : INF;
            ll bVal = validB ? recv : INF;
            return {aVal, bVal};
        } else {
            auto [idx, myVal] = myRankInfo(rankB);
            ll recv = shareIndex(idx);

            ll aVal = validA ? recv : INF;
            ll bVal = validB ? myVal : INF;
            return {aVal, bVal};
        }
    }

    // One side is empty.
    // The owner of the answer sends the answer value once.
    void finishFromSide(bool answerIsInAlice, int rank) {
        ll ans = -1;
        int idx = dummyIndex();

        if (isAlice == answerIsInAlice) {
            auto [sendIdx, val] = myRankInfo(rank);
            idx = sendIdx;
            ans = val;
        }

        ll recv = shareIndex(idx);

        if (isAlice != answerIsInAlice) {
            ans = recv;
        }

        answerAndContinue(ans);
    }

    void solveCase() {
        sort(S.begin(), S.end(), [](const Item &a, const Item &b) {
            if (a.val != b.val) return a.val < b.val;
            return a.idx < b.idx;
        });

        da = db = 0;
        k_rank = (N + M + 1) / 2;

        while (true) {
            if (lenA() == 0) {
                finishFromSide(false, k_rank); // answer is in Bob
                return;
            }

            if (lenB() == 0) {
                finishFromSide(true, k_rank); // answer is in Alice
                return;
            }

            if (k_rank <= 3) {
                vector<ll> cand;

                for (int r = 1; r <= k_rank; r++) {
                    auto [av, bv] = exchangeRanks(r, r);
                    if (av < INF) cand.push_back(av);
                    if (bv < INF) cand.push_back(bv);
                }

                sort(cand.begin(), cand.end());
                answerAndContinue(cand[k_rank - 1]);
                return;
            }

            int t = k_rank / 2;
            int p = min(t, lenA());
            int q = min(t, lenB());

            auto [ap, bq] = exchangeRanks(p, q);

            // 重複ありでも、等号時は Alice 側を捨てる、と固定すればよい。
            if (ap <= bq) {
                da += p;
                k_rank -= p;
            } else {
                db += q;
                k_rank -= q;
            }
        }
    }
};

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

    int T, Q;
    string player;

    cin >> T >> Q;
    cin >> player;

    bool isAlice = (player == "Alice");

    for (int tc = 0; tc < T; tc++) {
        int N, M;
        cin >> N >> M;

        int L = isAlice ? N : M;

        vector<Item> S(L);
        for (int i = 0; i < L; i++) {
            cin >> S[i].val;
            S[i].idx = i + 1;
        }

        Solver solver;
        solver.isAlice = isAlice;
        solver.N = N;
        solver.M = M;
        solver.S = move(S);

        solver.solveCase();
    }

    return 0;
}