結果

問題 No.3627 Share the Median
コンテスト
ユーザー 👑 loop0919
提出日時 2026-07-20 00:45:34
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 185 ms / 1,000 ms
+ 2µs
コード長 2,893 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 231 ms
コンパイル使用メモリ 95,972 KB
実行使用メモリ 79,160 KB
平均クエリ数 9.98
最終ジャッジ日時 2026-08-14 20:52:31
合計ジャッジ時間 8,127 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
純コード判定待ち
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
Sample 0 %
Easy 20 % AC * 16
Hard 80 % AC * 24
合計 3 * 100% = 300 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys


def main() -> None:
    player = input().strip()
    Q = int(input())
    N, M = map(int, input().split())
    X = list(map(int, input().split()))

    # (value, original_index), sorted by value and then by original index.
    sorted_x = sorted((value, index) for index, value in enumerate(X))

    share_count = 0

    def share_sorted_position(pos: int) -> int:
        """Share the element at sorted rank pos (0-indexed)."""
        nonlocal share_count

        original_index = sorted_x[pos][1]
        print("share", original_index + 1, flush=True)
        share_count += 1

        received = int(input())
        if received == -1:
            sys.exit(0)
        return received

    def finish(value: int) -> None:
        print("answer", value, flush=True)
        sys.exit(0)

    # Find the k-th smallest value in the union, where k is 1-indexed.
    a_left = 0
    b_left = 0
    k = (N + M + 1) // 2

    # In each round, compare up to floor(k/2)-th remaining elements.
    # If an array is not exhausted, k becomes at most ceil(k/2).
    while k > 1 and a_left < N and b_left < M:
        take_a = min(N - a_left, k // 2)
        take_b = min(M - b_left, k // 2)

        if player == "Alice":
            my_pos = a_left + take_a - 1
        else:
            my_pos = b_left + take_b - 1

        my_value = sorted_x[my_pos][0]
        other_value = share_sorted_position(my_pos)

        if player == "Alice":
            a_value = my_value
            b_value = other_value
        else:
            a_value = other_value
            b_value = my_value

        # The fixed tie-break makes both processes discard Alice's prefix
        # when the compared values are equal.
        if a_value <= b_value:
            a_left += take_a
            k -= take_a
        else:
            b_left += take_b
            k -= take_b

    # One final share makes the answer known to both players.
    if a_left == N:
        # The answer is the k-th remaining element of B.
        b_pos = b_left + k - 1
        if player == "Bob":
            answer_value = sorted_x[b_pos][0]
            share_sorted_position(b_pos)
        else:
            answer_value = share_sorted_position(0)  # Dummy A element.
        finish(answer_value)

    if b_left == M:
        # The answer is the k-th remaining element of A.
        a_pos = a_left + k - 1
        if player == "Alice":
            answer_value = sorted_x[a_pos][0]
            share_sorted_position(a_pos)
        else:
            answer_value = share_sorted_position(0)  # Dummy B element.
        finish(answer_value)

    # Neither array is exhausted, so k == 1.
    if player == "Alice":
        my_pos = a_left
    else:
        my_pos = b_left

    my_value = sorted_x[my_pos][0]
    other_value = share_sorted_position(my_pos)
    finish(min(my_value, other_value))


if __name__ == "__main__":
    main()
0