結果

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

ソースコード

diff # 

#!/usr/bin/env python3
# GPT Interactive solution with '? / !' protocol
# 2-D rectangle queries (≤ 8000) to locate ≤ 100 unknown points (0-1e6)

import sys
from collections import deque

# ────────── 問題定数 ─────────────────────────────
COORD_MIN = 0
COORD_MAX = 1_000_000
QUERY_LIMIT = 8000
# ────────────────────────────────────────────────

query_cnt = 0            # 送信済みクエリ数
points = []              # 発見した点 (x, y)

# ────────── 1 回問い合わせる関数 ────────────────
def ask(x1: int, x2: int, y1: int, y2: int) -> bool:
    """
    矩形 [x1,x2]×[y1,y2] に点が存在するか質問し，
    True / False を返す．
    """
    global query_cnt
    if query_cnt >= QUERY_LIMIT:
        sys.exit(0)      # これ以上は TLE/WA になるので終了

    # '?' プレフィックス
    print(f"? {x1} {x2} {y1} {y2}", flush=True)
    query_cnt += 1

    ans_line = sys.stdin.readline()
    if not ans_line:
        sys.exit(0)      # EOF ⇒ 終了
    ans = int(ans_line)

    if ans == -1:        # 不正・上限超過
        sys.exit(0)
    return ans == 1
# ────────────────────────────────────────────────


def main() -> None:
    # 四分木（大きい辺方向を常に半分）で分割探索
    q: deque[tuple[int, int, int, int]] = deque()
    q.append((COORD_MIN, COORD_MAX, COORD_MIN, COORD_MAX))

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

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

        # 長いほうを分割
        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