結果

問題 No.3161 Find Presents
ユーザー kencho
提出日時 2025-05-05 21:03:57
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 349 ms / 4,000 ms
コード長 2,916 bytes
コンパイル時間 232 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 27,768 KB
平均クエリ数 3399.66
最終ジャッジ日時 2025-05-05 21:13:18
合計ジャッジ時間 19,231 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env python3
# 2-D interactive search (≤ 100 points) with ≤ 8000 rectangle queries.
# protocol:  "? x1 x2 y1 y2"  ←→  judge: 1 / 0 / -1
#            "! N"            →  judge: expects N lines "Xi Yi"

import sys
from collections import deque

# ───── 定数 ───────────────────────────────────────
MIN_C, MAX_C = 0, 1_000_000      # 座標範囲
QUERY_LIMIT  = 8000              # 上限クエリ数
# ────────────────────────────────────────────────

query_cnt = 0                    # 送信したクエリ数
points    = []                   # 発見した点

# ───── 質問関数 ─────────────────────────────────
def ask(x1: int, x2: int, y1: int, y2: int) -> bool:
    """
    矩形 [x1,x2] × [y1,y2] に少なくとも 1 点が存在するかを尋ねる。
    True なら存在、False なら存在しない。
    """
    global query_cnt
    if query_cnt >= QUERY_LIMIT:
        sys.exit(0)              # これ以上は違反

    print(f"? {x1} {x2} {y1} {y2}", flush=True)
    query_cnt += 1

    resp_line = sys.stdin.readline()
    if not resp_line:
        sys.exit(0)              # EOF
    resp = int(resp_line)
    if resp == -1:               # 不正・回数超過通知
        sys.exit(0)
    return resp == 1
# ────────────────────────────────────────────────


def main() -> None:
    # 四分木探索：必ず 1 点以上含む矩形だけをキューに保持
    q: deque[tuple[int, int, int, int]] = deque(
        [(MIN_C, MAX_C, MIN_C, MAX_C)]
    )

    while q:
        x1, x2, y1, y2 = q.pop()

        # 1 格子点に確定
        if x1 == x2 and y1 == y2:
            points.append((x1, y1))
            continue

        # 長い辺方向を 2 分割
        if (x2 - x1) >= (y2 - y1):
            xm = (x1 + x2) // 2
            # 左半分
            if ask(x1, xm, y1, y2):
                q.append((x1, xm, y1, y2))
            # 右半分
            if xm + 1 <= x2 and ask(xm + 1, x2, y1, y2):
                q.append((xm + 1, x2, y1, y2))
        else:
            ym = (y1 + y2) // 2
            # 下半分
            if ask(x1, x2, y1, ym):
                q.append((x1, x2, y1, ym))
            # 上半分
            if ym + 1 <= y2 and ask(x1, x2, ym + 1, y2):
                q.append((x1, x2, ym + 1, y2))

    # ───── 解答出力 ─────────────────────────────
    print(f"! {len(points)}", flush=True)
    for x, y in points:
        print(f"{x} {y}", flush=True)


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