Last Rook

题目描述

这是一个交互式任务（你的程序通过标准输入输出与裁判程序交互）。 我们有一个 $N$ 乘 $N$ 的棋盘和 $N$ 个车。下面，棋盘中从上数第 $i$ 行、从左数第 $j$ 列的格子记作 $(i, j)$。
考虑将这些车放在棋盘的格子上。在这里，你需要将车放置，使得下列所有条件都满足。

每一行不包含两个或以上的车。 每一列不包含两个或以上的车。

现在，棋盘上已经放置了 $N-1$ 个车，且满足上述所有条件。你将选择一个当前没有车的格子并在该格子放置一枚车。（可以证明至少存在一个格子可以放置车以满足条件。） 但是，你不能直接看到哪些格子上有车。
取而代之，你最多可以向裁判询问 20 个问题，询问格式如下。

你选择整数 $A, B, C, D$，满足 $1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N$，并询问位于由满足 $A \leq i \leq B, C \leq j \leq D$ 的格子所形成的矩形区域内的车的数量。

找到一个可以放置车的格子。

输入格式

输出格式

提示

$2 \leq N \leq 10^3$ $N$ 为整数。这是一个交互式任务（你的程序通过标准输入输出与裁判程序交互）。 首先，从标准输入读取棋盘的大小 $N$。 $N$

接下来，重复询问问题直到找到一个可以放置车的格子。
一个问题应按以下格式打印到标准输出： $?$ $A$ $B$ $C$ $D$

裁判将以如下格式在标准输入给出回应： $T$

其中，$T$ 是该问题的回答，若问题无效或询问次数超过 $20$ 次则为 $-1$。 当裁判返回 $-1$ 时，提交将被视为错误。在这种情况下，程序应立即终止。 当你找到一个可以放置车的格子时，设该格子为 $(X, Y)$，并按以下格式输出答案。然后程序应立即终止。 $!$ $X$ $Y$

如果存在多个合适的答案，任意一个都将被接受。每次打印输出时，结尾都要换行并刷新标准输出。否则，可能会得到 TLE 判定。 如果在交互过程中打印了无效的输出，判定将不确定。 在打印答案后立即终止程序。否则，判定将不确定。下面是一个交互示例，其中 $N=3$ 且车放在 $(1, 2)$ 和 $(2, 1)$。

标签: AtCoder|abc269E

来源

AtCoder|abc269E