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

• 問題: No.3627 Share the Median
• ユーザー: 👑 loop0919
• 提出日時: 2026-06-10 01:21:24
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: RE
• 実行時間: -
• コード長: 4,236 bytes
• コンパイル時間: 2,092 ms
• コンパイル使用メモリ: 352,180 KB
• 実行使用メモリ: 9,548 KB
• 平均クエリ数: 1.00
• 最終ジャッジ日時: 2026-08-14 20:51:12
• 合計ジャッジ時間: 9,858 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

サブタスク	配点	結果
Sample	0 %
Easy	20 %	RE * 16
Hard	80 %	RE * 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
};

string Player;
int Q, N, M;
vector<Item> S; // my sorted sequence
bool isAlice;

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

int lenA() { return N - da; }
int lenB() { return M - db; }

[[noreturn]] void finish_answer(ll x) {
    cout << "answer " << x << endl;
    cout.flush();
    exit(0);
}

ll share_index(int idx) {
    cout << "share " << idx << endl;
    cout.flush();

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

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

// rank-th value/index in my current remaining sequence.
// rank is 1-indexed among the remaining elements.
pair<int, ll> my_rank_info(int rank) {
    int offset = isAlice ? da : db;
    int len = isAlice ? lenA() : lenB();

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

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

    if (isAlice) {
        auto [idx, myVal] = my_rank_info(rankA);
        ll recv = share_index(idx);
        ll aVal = validA ? myVal : INF;
        ll bVal = validB ? recv : INF;
        return {aVal, bVal};
    } else {
        auto [idx, myVal] = my_rank_info(rankB);
        ll recv = share_index(idx);
        ll aVal = validA ? recv : INF;
        ll bVal = validB ? myVal : INF;
        return {aVal, bVal};
    }
}

// One side is empty.
// The owner of the answer sends it once; the other side sends a dummy.
[[noreturn]] void finish_from_side(char side, int rank) {
    ll ans = -1;
    int idx = dummy_index();

    if ((side == 'A') == isAlice) {
        auto [sendIdx, val] = my_rank_info(rank);
        idx = sendIdx;
        ans = val;
    }

    ll recv = share_index(idx);

    if ((side == 'A') != isAlice) {
        ans = recv;
    }

    finish_answer(ans);
}

[[noreturn]] void solve_small() {
    if (k_rank == 1) {
        auto [a1, b1] = exchange_ranks(1, 1);
        finish_answer(min(a1, b1));
    }

    if (k_rank == 2) {
        auto [a1, b1] = exchange_ranks(1, 1);
        auto [a2, b2] = exchange_ranks(2, 2);

        vector<ll> v;
        if (a1 < INF) v.push_back(a1);
        if (a2 < INF) v.push_back(a2);
        if (b1 < INF) v.push_back(b1);
        if (b2 < INF) v.push_back(b2);

        sort(v.begin(), v.end());
        finish_answer(v[1]);
    }

    // k_rank == 3
    auto [a2, b2] = exchange_ranks(2, 2);

    ll ans;

    if (a2 < b2) {
        auto [a3, b1] = exchange_ranks(3, 1);

        if (b1 < a2) {
            ans = a2;
        } else {
            ans = min(a3, b1);
        }
    } else {
        auto [a1, b3] = exchange_ranks(1, 3);

        if (a1 < b2) {
            ans = b2;
        } else {
            ans = min(a1, b3);
        }
    }

    finish_answer(ans);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> Q;
    cin >> Player;
    cin >> N >> M;

    isAlice = (Player == "Alice");

    int L = isAlice ? N : M;
    S.resize(L);

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

    sort(S.begin(), S.end(), [](const Item &a, const Item &b) {
        return a.val < b.val;
    });

    k_rank = (N + M + 1) / 2;

    while (true) {
        if (lenA() == 0) {
            finish_from_side('B', k_rank);
        }
        if (lenB() == 0) {
            finish_from_side('A', k_rank);
        }

        if (k_rank <= 3) {
            solve_small();
        }

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

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

		if (ap < bq) {
		    da += p;
		    k_rank -= p;
		} else {
		    db += q;
		    k_rank -= q;
		}
    }
}