#include 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 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 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 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 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; } } }