Siyuan

「Codeforces 1153E」Serval and Snake
「Codeforces 1153E」Serval and Snake
扫描右侧二维码阅读全文
29
2019/04

「Codeforces 1153E」Serval and Snake

题目链接: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;
}
最后修改:2019 年 06 月 28 日 01 : 12 PM

发表评论