AT_abc269_e [ABC269E] Last Rook

[problemUrl]: https://atcoder.jp/contests/abc269/tasks/abc269_e **本题为交互题**（你的程序需要与评测程序通过输入输出进行交互）。 有一个 $N \times N$ 的国际象棋棋盘和 $N$ 个车（Rook）棋子。下面将棋盘从上到下第 $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$ 组成的矩形区域内有多少个车。 请找出可以放置车的格子。

本题为交互题（你的程序需要与评测程序通过输入输出进行交互）。 首先，你需要从标准输入读取棋盘的大小 $N$。 > $N$ 接下来，在找到可以放置车的格子之前，你可以多次进行询问。 每次询问，请按如下格式输出到标准输出： > ? $A$ $B$ $C$ $D$ 评测系统会返回如下格式的响应： > $T$ 其中，$T$ 是你询问的区域内的车的数量。如果你进行了非法询问，或者询问次数超过 $20$ 次，则 $T$ 会为 $-1$。 如果评测系统返回 $-1$，则你的提交已被判为不正确，此时请立即终止程序。 当你找到可以放置车的格子后，请将该格子的坐标 $(X,\,Y)$ 按如下格式输出，并立即终止程序： > ! $X$ $Y$ 如果有多个答案，输出任意一个都视为正确。

无

## 限制 - $2 \leq N \leq 10^3$ - $N$ 为整数 ## 注意事项 - **每次输出后，请在末尾加上换行并刷新标准输出。否则可能会被判为 TLE。** - **交互过程中如果输出不合法，评测结果不确定。** - 输出答案后请立即终止程序，否则评测结果不确定。 ## 输入输出样例 以下是 $N=3$，且 $(1,\,2),\,(2,\,1)$ 已经有车的输入输出示例。 输入 输出 说明 `3` 首先给出整数 $N$。 `? 1 2 1 3` 询问 $(A,B,C,D)=(1,2,1,3)$ 区域。 `2` 回答为 $2$，表示该区域有 $2$ 个车。 `? 2 3 1 1` 询问 $(A,B,C,D)=(2,3,1,1)$ 区域。 `1` 回答为 $1$，表示该区域有 $1$ 个车。 `? 1 3 3 3` 询问 $(A,B,C,D)=(1,3,3,3)$ 区域。 `0` 回答为 $0$，表示该区域没有车。 `! 3 3` 确定答案为 $(3,\,3)$，输出即可。 由 ChatGPT 4.1 翻译