ABC269E - Last Rook

考え方

$i$軸のうち，どの$j$座標にもルークが含まれないのは1つだけである．したがって，「$(A, B, 1, N)$を聞いたときに$B - A - 1$が帰って来ること」が「$A \leq X \leq B$」の必要十分条件である．よって，二分探索で$X$を求めることができる．

同様に，「$(1, N, C, D)$を聞いたときに$D - C - 1$が帰って来ること」が「$C \leq Y \leq D$」の必要十分条件である．

回答例

N = int(input())

A, B = 1, N
while B - A > 0:
    mid = (A + B) // 2
    print(f'? {A} {mid} 1 {N}')
    T = int(input())
    if T == -1:
        raise RuntimeError('')
    if T < mid - A + 1:
        B = mid
    else:
        A = mid + 1

C, D = 1, N
while D - C > 0:
    mid = (C + D) // 2
    print(f'? 1 {N} {C} {mid}')
    T = int(input())
    if T == -1:
        raise RuntimeError('')
    if T < mid - C + 1:
        D = mid
    else:
        C = mid + 1

exit(print(f'! {A} {C}'))