题目链接:Codeforces 1153E
这是一道交互题。
Serval 在上学的途中,必须穿过一个池塘,池塘里面有一条危险的蛇。池塘可以用一张 $n \times n$ 的网格表示。蛇的头部和尾部在不同的格子里,它的身体是一串连接头部和尾部的格子,并且身体不会相交。Serval 碰到蛇就会有生命危险。
幸运的是,他有一个特殊的装置可以回答如下问题:你可以选择一个矩形,它会告诉你蛇身穿过矩形边界的次数。
你作为 Serval 的好朋友,请你在使用不超过 $2019$ 询问后帮 Serval 找到蛇头和蛇尾。注意:蛇不会随着询问而移动。
数据范围:$2 \le n \le 1000$。
Solution
对于任意一个矩形,询问分为三种情况:
- 如果蛇头和蛇尾都不在矩形内,那么答案为偶数。
- 如果头尾的其中一者在矩形内,那么答案为奇数。
- 如果蛇头和蛇尾全都在矩形内,那么答案为偶数。
这样一来,我们对每行每列询问,得到蛇头和蛇尾所在的行(或列),然后对得到的行(或列)二分查找目标所在位置。
注意到直接这样查询,次数被卡满时为 $n + n + \log n + \log n \le 2020$。其中我们不需要询问最后一行、最后一列也可以得到其奇偶性,故询问次数上界为 $2018$。
时间复杂度:$\mathcal O(n)$。
Code
#include <cstdio>
const int N = 1e3 + 5;
int n, t[N], a[N], b[N];
int query(int x1, int y1, int x2, int y2) {
printf("? %d %d %d %d\n", x1, y1, x2, y2);
fflush(stdout);
int x;
scanf("%d", &x);
return x;
}
void answer(int x1, int y1, int x2, int y2) {
printf("! %d %d %d %d\n", x1, y1, x2, y2);
fflush(stdout);
}
int solveRow(int x) {
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
query(x, 1, x, mid) & 1 ? r = (ans = mid) - 1 : l = mid + 1;
}
return ans;
}
int solveCol(int x) {
int l = 1, r = n, ans = 0;
while (l <= r) {
int mid = (l + r) >> 1;
query(1, x, mid, x) & 1 ? r = (ans = mid) - 1 : l = mid + 1;
}
return ans;
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) t[i] = query(i, 1, i, n) - t[i - 1];
for (int i = 1; i <= n; i++) a[i] = t[i - 1] + t[i];
for (int i = 1; i < n; i++) t[i] = query(1, i, n, i) - t[i - 1];
for (int i = 1; i <= n; i++) b[i] = t[i - 1] + t[i];
bool flg = false;
for (int i = 1; i <= n; i++) if (a[i] & 1) flg = true;
int tot = 0, ans[3][2];
if (flg) {
for (int i = 1; i <= n; i++) {
if (a[i] & 1) ans[++tot][0] = i, ans[tot][1] = solveRow(i);
}
} else {
for (int i = 1; i <= n; i++) {
if (b[i] & 1) ans[++tot][1] = i, ans[tot][0] = solveCol(i);
}
}
answer(ans[1][0], ans[1][1], ans[2][0], ans[2][1]);
return 0;
}