← 返回题目列表

Codeforces · 2090/C

C. 餐厅

中文机器翻译题面 查看原题

偌大的王国内部,有一个无限大的餐厅。它可以表示为一组单元格 ($$$x, y$$$),其中 $$$x$$$ 和 $$$y$$$ 是非负整数。大厅里有无数张桌子。每个表占用四个单元格 ($$$3x + 1, 3y + 1$$$)、($$$3x + 1, 3y + 2$$$)、($$$3x + 2, 3y + 1$$$)、($$$3x + 2, 3y + 2$$$),其中 $$$x$$$ 和 $$$y$$$ 是任意非负整数。所有不属于任何表格的单元格都是走廊。

有$$$n$$$客人一一来到餐厅。每个客人出现在单元格 $$$(0, 0)$$$ 中并且想要到达表格单元格。只需一步,他们就可以移动到任何相邻的地方 走廊 细胞,并在他们的 最后 步骤,他们必须移动到相邻的空闲位置 表 细胞。他们占据所选的桌子单元格,其他客人不能移动到那里。

每个客人都有一个特征 $$$t_i$$$,可以是 $$$0$$$ 或 $$$1$$$。他们按顺序进入大厅,从牢房开始步行($$$0, 0$$$)。如果 $$$t_i=1$$$,则第 $$$i$$$ 位客人走到最近的空桌子单元格。如果 $$$t_i=0$$$,他们会走到属于完全空闲表格的最近的表格单元格。请注意,其他客人稍后可能会选择同一张桌子。

距离定义为到达表格单元格所需的最小步数。如果有多个表格单元格距离相同,则客人选择 $$$x$$$ 最小的单元格,如果仍然存在平局,则选择 $$$y$$$ 最小的单元格。

对于每位客人,找到他们选择的表格单元格。

输入

第一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 5000$$$) — 测试用例的数量。然后是他们的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50\,000$$$) — 客人数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$t_1, t_2, \ldots, t_n$$$ ($$$t_i \in \{0, 1\}$$$) — 客人的特征。

保证所有测试用例的$$$n$$$总和不超过$$$50\,000$$$。

输出

对于每个测试用例,输出 $$$n$$$ 行 - 对于每个客人,他们所在的单元格。

示例

输入
复制

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

输出
复制

1 1
1 2
2 1
1 4
4 1
1 5
1 1
1 4
4 1
1 2
2 1

注意

考虑第一个测试用例:

第一个客人到牢房 ($$$1, 1$$$) 的距离是 $$$2$$$,所以他坐在那里。

第二位客人到单元格 ($$$1, 2$$$) 的距离是 $$$3$$$,到单元格 ($$$2, 1$$$) 的距离也是 $$$3$$$,但由于第一个选项的第一个坐标较小,所以他会选择它。

第三位客人到单元格($$$2, 1$$$)的距离是$$$3$$$,所以他会选择它。

第四位客人到单元格($$$1, 4$$$)的距离是$$$5$$$,他会选择它。

从第五位客人到牢房 ($$$4, 1$$$) 的距离是 $$$5$$$。

第六位客人到单元格($$$1, 5$$$)的距离是$$$6$$$,到单元格($$$2, 2$$$)的距离也是$$$6$$$,但由于第一个坐标较小,所以他会选择第一个选项。