4281. [THUPC 2025 Final] 食堂

【题目背景】

……所以为什么会有两道食堂题？

【题目描述】

有一个位于第一象限的食堂。

食堂被划分为若干个 $1\times 1$ 的区域，区域 $(x,y)$ 为以 $(x,y),(x,y+1),(x+1,y),(x+1,y+1)$ 为顶点的正方形。称两个区域 $(x_1,y_1)$ 和 $(x_2,y_2)$ 相邻当且仅当 $|x_1-x_2|+|y_1-y_2|=1$。

区域有两种类型，一种是可供顾客自由走动的过道，另一种是可供顾客坐下用餐的座位。食堂里的座位非常多，而且排布得很有规律：所有满足 $x\bmod 3\ne 0$ 且 $y\bmod 3\ne 0$ 的区域 $(x,y)$ 是座位，其他区域都是过道。四个相连的座位构成一张餐桌。

从上空俯瞰，食堂中座位的排布方式如下图：

在过道上，顾客可以自由移动。具体地，如果顾客当前位于过道 $(x,y)$，他可以走一步，移动到相邻的区域。如果顾客移动到了座位，他就会在此坐下。

顾客对座位的偏好可以用容忍度 $o\in\{0,1,2\}$ 来描述，其中：

• $o=0$ 的顾客只愿意坐到对应餐桌没有人的空座位上吃饭。
• $o=1$ 的顾客只愿意坐到相邻座位没有人的空座位上吃饭。
• $o=2$ 的顾客愿意坐在任何空座位上吃饭。

当一个顾客坐下之后，他就会专注地吃饭，就算有其他顾客出现，导致当前的座位变成他不愿意坐的座位，他也不会因此离开。

最开始的时候，餐厅里一个顾客也没有。接下来依次发生了 $q$ 个事件，每个事件是以下两种之一：

• - 第一种事件：具有某个容忍度 $o$ 的顾客从区域 $(0,0)$ 进入餐厅，他会寻找移动步数最少的、他愿意坐的座位坐下，如果这样的座位有多个，顾客会选择 $x$ 坐标最小的，如果还有多个则会选择 $y$ 坐标最小的。

第二种事件：座位 $(x,y)$ 的状态发生了变化，如果原来有顾客坐在这里，这个顾客会立刻离开餐厅；如果原来这个座位上没有顾客，则会出现一个顾客坐在这里。

你需要对于第一种事件求出顾客选择的座位，对于第二种事件求出是有人离开还是有人坐下。

【输入格式】

第一行一个正整数 $q\ (1\le q\le5\times10^5)$。

接下来 $q$ 行，每行先是一个整数 $t\in\{1,2\}$，表示事件种类。

当 $t=1$ 时，接下来读入一个整数 $o\in\{0,1,2\}$，表示来了一位容忍度为 $o$ 的顾客。

当 $t=2$ 时，接下来读入两个正整数 $x,y\ (1\le x,y\le10^4)$，满足 $x\bmod3\in\{1,2\}$ 与 $y\bmod3\in\{1,2\}$，表示座位 $(x,y)$ 的状态发生了变化。

【输出格式】

对每个操作输出一行。

• 对于 $t=1$ 的操作，依次输出两个整数 $x,y$，表示顾客坐到了座位 $(x,y)$。
• 对于 $t=2$ 的操作，如果该座位上有人，输出 out，否则输出 in。

【输入样例】

10
1 0
1 0
2 1 1
2 2 2
1 0
1 1
1 2
1 2
1 2
1 1

【输出样例】

1 1
1 4
out
in
4 1
1 1
1 2
2 1
1 5
1 7

【样例解释】

以下图片展示了每一步操作影响的位置。数字标识了操作的编号。