「2025 ICPC 网络赛 1」F. Robot

    「2025 ICPC 网络赛 1」F. Robot

    QOJ 14306

    This is an interactive problem.

    一个机器人在一个无限大的二维平面的第一象限内移动。最初机器人位于坐标 (sx,sy)(s_x, s_y)。最初所有单元格都是白色的。

    游戏包含了若干次操作,最多 T=1000T = 1000 次操作。每次操作都会按照以下顺序发生事件:

    1. 你的操作:你可以选择一个整点坐标 (x,y)(x, y),其中 1≤x,y≤T1 \leq x, y \leq T,你会将该单元格标记成黑色。
    2. 机器人的操作:机器人可以移动到与其所在单元格八连通的单元格(由交互器决策)。
    3. 结果检查:机器人移动到下一个单元格之后,系统会检查该单元格是否是黑色。
    • 如果是黑色,机器人爆炸。
    • 如果是白色,则进行下一次操作。

    你的目标是在 TT 次操作之内使机器人爆炸。

    数据范围:1≤sx,sy≤201 \leq s_x, s_y \leq 20。

    时空限制:22s / 10241024MiB。

    Solution

    基础的想法是,先构造一个正方形边界将机器人框住,再对框住的矩形内部进行查杀。

    尝试构造一个 100×100100 \times 100 的正方形边界。发现我们一开始不能将所有的边界都填充过去,这样机器人会在我们填充边界的过程中提前逃出边界。所以考虑先构造边界的一部分。

    具体的,先将右上角 (100,100)(100, 100) 填充,然后以右上角为起点,向左和向下每间隔 22 个单元格填充一个黑点。这样,等到机器人想要从某个缺口突破时,我们再将这个缺口填充。同时,右上角的部分,向上和向右有两个缺口,我们先将这两个缺口都填充了。此时只用了 7171 步。机器人最远只能逃到 (91,91)(91, 91)。

    接下来依次将边界填充完整。但是在机器人将要从一个缺口突破时,需要优先将这个缺口填充。具体地,对于向上的方向,机器人可能会从 (x,100),(x−1,100),(x+1,100)(x, 100), (x - 1, 100), (x + 1, 100) 这三个位置进行突破,于是当 y≥97y \geq 97 时,我们就要依次判断这三个位置是否需要堵住了,恰好留有三步的容错。向右同理(由于已经将最右上角的两个缺口填充,所以向上和向右是互不干扰的)。

    将边界填充完整之后,考虑对框住的矩形内部进行查杀。我们大可不必 99×9999 \times 99 地毯式查杀。考虑每次对于框住的矩形区域,取出最长的一条边,填充这条边的中线。然后对剩下的矩形继续进行操作,直到只剩下 1×11\times 1 的矩形为止。设边长为 LL,则所需要的步数为 L+L2+L2+L4+L4+⋯=O(L)L + \frac{L}{2} + \frac{L}{2} + \frac{L}{4} + \frac{L}{4} + \dots = \mathcal{O}(L)。

    #include <bits/stdc++.h>
    
    #define debug(a) std::cout << #a << "=" << (a) << ' '
    
    using s64 = long long;
    using u64 = unsigned long long;
    
    /* 取 min */
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    /* 取 max */
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    /* ----- ----- ----- 正文 ----- ----- ----- */
    
    int px, py;
    
    int vis[1001][1001];
    
    int color(int x, int y) {
        if (x < 1 || x > 1000 || y < 1 || y > 1000) return 0;
        if (vis[x][y]) return 0;
    
        vis[x][y] = 1;
        std::cout << x << ' ' << y << std::endl;
    
        std::cin >> px >> py; if (!px) exit(0);
        return 1;
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        std::cin >> px >> py; if (!px) exit(0);
    
        color(100, 100);
        
        for (int i = 97; i >= 1; i -= 3) {
            color(i, 100);
            color(100, i);
        }
    
        color(99, 100);
        color(98, 100);
        color(100, 99);
        color(100, 98);
    
        for (;;) {
            if (px >= 97) {
                if (color(100, py)) continue;
                if (color(100, py + 1)) continue;
                if (color(100, py - 1)) continue;
            }
            if (py >= 97) {
                if (color(px, 100)) continue;
                if (color(px + 1, 100)) continue;
                if (color(px - 1, 100)) continue;
            }
    
            int flag = 1;
            for (int i = 1; i <= 100; i ++) {
                if (color(i, 100)) { flag = 0; break; }
                if (color(100, i)) { flag = 0; break; }
            }
    
            if (flag) break;
        }
    
        int sx = 1, ex = 99, sy = 1, ey = 99;
        while (sx < ex || sy < ey) {
            if (ex - sx > ey - sy) {
                int mid = (sx + ex) >> 1;
                for (int j = sy; j <= ey; j ++) {
                    color(mid, j);
                }
                if (px < mid) {
                    ex = mid - 1;
                } else {
                    sx = mid + 1;
                }
            } else {
                int mid = (sy + ey) >> 1;
                for (int i = sx; i <= ex; i ++) {
                    color(i, mid);
                }
                if (py < mid) {
                    ey = mid - 1;
                } else {
                    sy = mid + 1;
                }
            }
        }
    
        color(sx, sy);
    
        return 0;
    }
    
    /**
     *  心中无女人
     *  比赛自然神
     *  模板第一页
     *  忘掉心上人
    **/