結果

問題 No.3161 Find Presents
ユーザー kencho
提出日時 2025-05-05 20:40:24
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 3,386 bytes
コンパイル時間 414 ms
コンパイル使用メモリ 12,348 KB
実行使用メモリ 28,024 KB
平均クエリ数 1.00
最終ジャッジ日時 2025-05-05 21:12:13
合計ジャッジ時間 8,550 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 80
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

import sys
from collections import deque

# ----- parameters ------------------------------------------------------------
COORD_MIN = 0
COORD_MAX = 1_000_000
QUERY_LIMIT = 8000
# -----------------------------------------------------------------------------

query_cnt = 0                      # 送信した質問数
points    = []                     # 発見した (x, y)

# ──────────────────────────────────────────────────────────────────────────────
def ask(x1: int, x2: int, y1: int, y2: int) -> bool:
    """
    1 回質問する．矩形 [x1,x2] × [y1,y2] 内に点が存在すれば True を返す．
    ジャッジが -1 を返した場合は即座に exit(0) する．
    """
    global query_cnt
    if query_cnt >= QUERY_LIMIT:
        sys.exit(0)                # これ以上質問するとペナルティなので強制終了

    print(x1, x2, y1, y2, flush=True)
    query_cnt += 1

    try:
        resp = int(sys.stdin.readline())
    except Exception:
        sys.exit(0)                # 想定外の入力 ⇒ 終了

    if resp == -1:                 # 不正クエリ / 回数超過
        sys.exit(0)
    return resp == 1               # 1 → 存在する, 0 → 無い
# ──────────────────────────────────────────────────────────────────────────────


def main() -> None:
    # 最初の矩形 ([全域]) に点が存在するのは制約 N ≥ 1 で保証されているので，
    # 根ノードの存在判定クエリは不要．
    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()

        # 既に一点に絞られたら記録
        if x1 == x2 and y1 == y2:
            points.append((x1, y1))
            # 100 個そろえば終了してもよいが，キューが空になるまで走らせても
            # 問題ない（重複座標は無いことが保証されている）
            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(-1, flush=True)          # これ以降は答えの出力

    print(len(points), flush=True)
    for x, y in points:
        print(x, y, flush=True)


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