C. Dining Hall 详细题解

一、问题重述

无限大的餐厅网格，桌子由 $4$ 个单元格组成：

$$(3x+1,3y+1),\ (3x+1,3y+2),\ (3x+2,3y+1),\ (3x+2,3y+2) $$

其中 $x,y \ge 0$ 为非负整数。其他格子是走廊。

$n$ 位客人依次从 $(0,0)$ 出发，走到空闲的桌子单元格，最后一步必须从走廊邻接桌子。

每位客人有 $t_i \in \{0,1\}$：

• $t_i = 1$：选最近的空闲桌子单元格（距离 = 步数）
• $t_i = 0$：选最近的、属于完全空闲桌子的单元格（即该桌子的 4 个格子都未被占）

距离相同则选 $x$ 最小，再选 $y$ 最小。

对于每个客人，输出他们坐下的坐标。

---

二、核心思路

2.1 距离公式

通过 BFS 或数学推导可得，任意格子 $(x,y)$ 到 $(0,0)$ 的最短步数（只走走廊）为：

$$d(x,y) = x + y + 2 \cdot [x \bmod 3 = y \bmod 3 = 2] $$

即：如果 $x$ 和 $y$ 模 $3$ 都等于 $2$，则加 $2$，否则就是 $x+y$。

原因：$(0,0)$ 是走廊，每次可以沿走廊移动。只有进入桌子单元格的最后一步才允许从相邻走廊进入，所以内部路径长度就是曼哈顿距离，但若目标格子是 $(3k+2,3l+2)$ 这种“内部角落”，需要绕一下。

2.2 桌子单元格的排序

由于 $n \le 50000$，只需要考虑前 $4n$ 个距离最小的桌子单元格（因为每个客人最多占一个，且 $t=0$ 可能把一整桌 4 个格都占满）。

我们可以通过枚举 $k = x+y$ 从小到大的方式生成所有距离 $\le D$ 的桌子单元格，并按照 $(d, x, y)$ 排序。实际标程采用一种数学构造生成排序序列，存储在 Ord 数组中。

2.3 快速判断可用性

• 对于 $t=1$：只需该格子未被占
• 对于 $t=0$：该格子所属整张桌子（4 个格子）都未被占

标程用 G[0] 和 G[1] 两个布尔数组标记：

• G[1][pos]：该格子是否已被占用
• G[0][pos]：该格子是否不允许被 $t=0$ 的客人选（即其桌子的任一格子被占）

每次客人坐下后：

• 标记 G[1][pos] = 1
• 找出该格子所属桌子的另外 3 个格子（通过 Nxt 函数旋转），标记 G[0][them] = 1

2.4 贪心选择

对于每个客人，从排序好的 Ord 数组中，从当前指针 Ans[t] 开始向后找第一个 G[t][pos] == 0 的格子。

由于每次选择后指针只会向前移动，总复杂度 $O(n)$。

---

三、标程代码（带详细注释）

#include <bits/stdc++.h>
using namespace std;

using uint = unsigned int;
using bol = bool;

const uint T = 2000;        // 坐标范围的上界 (2000*2000 格子足够覆盖前 4n 个桌子)
const uint R = 200000;      // 最多需要的桌子数 (4*50000)

uint Ord[R + 5];            // 预排序的桌子单元格（编码为 x*T + y）

// 获取同一张桌子的另一个格子（旋转）
uint Nxt(uint p, uint o) {
    uint x = p / T, y = p % T;
    if (o & 1) y = y / 3 * 3 + 3 - y % 3;   // 同一行对称
    if (o & 2) x = x / 3 * 3 + 3 - x % 3;   // 同一列对称
    return x * T + y;
}

bol G[2][T * T];    // G[1][p]: 格子 p 是否被占; G[0][p]: 格子 p 是否被 t=0 禁止
uint Ans[2];        // 当前指针位置

int main() {
    // 预生成前 R 个最“近”的桌子单元格（按距离、x、y 排序）
    for (uint i = 2, tp = 0; i < T && tp < R; i++) {
        if (i % 3 == 2) {
            // 情况：i ≡ 2 (mod 3)
            for (uint x = 1; x < i && tp < R; x += 3)
                Ord[tp++] = x * T + i - x;
        } else if (i % 3 == 0) {
            // 情况：i ≡ 0 (mod 3)
            for (uint x = 1; x <= i - 2 && tp < R; x++) {
                if (x % 3 == 1)
                    Ord[tp++] = x * T + i - x;
                else if (x % 3 == 2) {
                    Ord[tp++] = x * T + i - x - 2;
                    Ord[tp++] = x * T + i - x;
                }
            }
            Ord[tp++] = (i - 1) * T + 1;
        }
    }

    uint q;
    scanf("%u", &q);
    while (q--) {
        uint n;
        scanf("%u", &n);
        // 重置前 4n 个格子的标记
        for (uint i = 0; i < n * 4; i++) {
            G[0][Ord[i]] = G[1][Ord[i]] = 0;
        }
        Ans[0] = Ans[1] = 0;

        while (n--) {
            uint t;
            scanf("%u", &t);
            // 跳过已被占或禁止的格子
            while (G[t][Ord[Ans[t]]]) Ans[t]++;

            uint pos = Ord[Ans[t]];
            uint x = pos / T, y = pos % T;
            printf("%u %u\n", x, y);

            // 标记该格子被占
            G[1][pos] = 1;
            // 标记该桌子的其他三个格子为 t=0 禁止
            for (uint o = 0; o < 4; o++) {
                G[0][Nxt(pos, o)] = 1;
            }
            Ans[t]++;   // 指针后移
        }
    }
    return 0;
}

---

四、算法复杂度

• 预处理 Ord 数组：$O(4n)$
• 每个测试用例：$O(n)$
• 总复杂度 $O(\sum n)$，满足要求

---

五、关键点总结

要点	说明
距离公式	$d = x + y + 2\cdot[x\bmod3=y\bmod3=2]$
排序生成	按 $x+y$ 递增，同距离按 $x,y$ 字典序
状态维护	两个标记数组，分别针对 $t=0$ 和 $t=1$
贪心选择	指针只增，总 $O(n)$
桌子对称	Nxt 函数快速获取同桌其他格子

---

六、示例验证

输入：

2
6
0 1 1 0 0 1
5
1 0 0 1 1

输出与题目示例完全一致 ✅

---

七、思维扩展

• 原始想法：用 BFS 计算每个格子距离，用优先队列维护最近可用格子
• 优化：由于距离公式简单且格子数量有限，可以预先生成排序序列
• $t=0$ 的处理：需要整张桌子空闲，因此每次占用后要封锁同桌其他格子

本题巧妙之处在于将无限网格转化为有限前缀，并用数学公式直接计算排序，避免了 BFS。