#1168838 (PyPy3) No.3627 Share the Median

• 問題: No.3627 Share the Median
• ユーザー: 👑 loop0919
• 提出日時: 2026-06-11 01:32:06
• 言語: PyPy3 (7.3.17)
• 結果: RE
  (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 4,031 bytes
• コンパイル時間: 221 ms
• コンパイル使用メモリ: 96,108 KB
• 実行使用メモリ: 94,316 KB
• 平均クエリ数: 1.00
• 最終ジャッジ日時: 2026-08-14 20:51:27
• 合計ジャッジ時間: 16,477 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

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

ソースコード

import sys

INF = 10 ** 30


def read_line():
    line = sys.stdin.readline()
    if not line:
        sys.exit(0)
    return line


class Solver:
    def __init__(self, is_alice, n, m, arr):
        self.is_alice = is_alice
        self.n = n
        self.m = m

        # (value, original 1-indexed index)
        self.s = [(v, i + 1) for i, v in enumerate(arr)]
        self.s.sort()

        self.da = 0
        self.db = 0
        self.k_rank = (n + m + 1) // 2

    def len_a(self):
        return self.n - self.da

    def len_b(self):
        return self.m - self.db

    def my_len(self):
        return self.len_a() if self.is_alice else self.len_b()

    def my_offset(self):
        return self.da if self.is_alice else self.db

    def dummy_index(self):
        return self.s[0][1]

    def share_index(self, idx):
        print(f"share {idx}", flush=True)

        line = read_line()
        v = int(line.strip())
        if v == -1:
            sys.exit(0)
        return v

    def answer_and_continue(self, ans):
        print(f"answer {ans}", flush=True)

        line = read_line()
        r = int(line.strip())
        if r == -1:
            sys.exit(0)

    def my_rank_info(self, rank):
        length = self.my_len()
        offset = self.my_offset()

        if 1 <= rank <= length:
            value, idx = self.s[offset + rank - 1]
            return idx, value
        else:
            return self.dummy_index(), INF

    def exchange_ranks(self, rank_a, rank_b):
        valid_a = 1 <= rank_a <= self.len_a()
        valid_b = 1 <= rank_b <= self.len_b()

        if self.is_alice:
            idx, my_val = self.my_rank_info(rank_a)
            recv = self.share_index(idx)

            a_val = my_val if valid_a else INF
            b_val = recv if valid_b else INF
            return a_val, b_val
        else:
            idx, my_val = self.my_rank_info(rank_b)
            recv = self.share_index(idx)

            a_val = recv if valid_a else INF
            b_val = my_val if valid_b else INF
            return a_val, b_val

    def finish_from_side(self, answer_is_in_alice, rank):
        ans = -1
        idx = self.dummy_index()

        if self.is_alice == answer_is_in_alice:
            idx, val = self.my_rank_info(rank)
            ans = val

        recv = self.share_index(idx)

        if self.is_alice != answer_is_in_alice:
            ans = recv

        self.answer_and_continue(ans)

    def solve_case(self):
        while True:
            if self.len_a() == 0:
                # answer is in Bob
                self.finish_from_side(False, self.k_rank)
                return

            if self.len_b() == 0:
                # answer is in Alice
                self.finish_from_side(True, self.k_rank)
                return

            if self.k_rank <= 3:
                cand = []

                for r in range(1, self.k_rank + 1):
                    av, bv = self.exchange_ranks(r, r)
                    if av < INF:
                        cand.append(av)
                    if bv < INF:
                        cand.append(bv)

                cand.sort()
                self.answer_and_continue(cand[self.k_rank - 1])
                return

            t = self.k_rank // 2
            p = min(t, self.len_a())
            q = min(t, self.len_b())

            ap, bq = self.exchange_ranks(p, q)

            # 重複ありでも、等号時は Alice 側を捨てる、と固定すればよい。
            if ap <= bq:
                self.da += p
                self.k_rank -= p
            else:
                self.db += q
                self.k_rank -= q


def main():
    first = read_line().split()
    t = int(first[0])
    q = int(first[1])

    player = read_line().strip()
    is_alice = player == "Alice"

    for _ in range(t):
        n, m = map(int, read_line().split())
        arr = list(map(int, read_line().split()))

        solver = Solver(is_alice, n, m, arr)
        solver.solve_case()


if __name__ == "__main__":
    main()