[AdditionalFile5236.zip](file://AdditionalFile5236.zip?type=additional_file)

#5236. 「UOI 2020 Stage 4 Day1」猜颜色

标签: 交互 | 时间限制: 6000 ms | 内存限制: 256 MiB |

题目描述

题目译自 Ukrainian Olympiads in Informatics 2020 Stage 4 Day1 T3. Вгадайте колір

给定 $n$ 个小球，编号从 $1$ 到 $n$。每个小球都有一个颜色，但你不知道具体颜色。总共有 $k$ 种不同的颜色。

你可以通过一次查询查看一个小球，并得知你已经查看过的同色小球的数量（包括当前这个小球）。但在这种查询中，你无法直接得知小球的颜色。你总共可以进行不超过 $c$ 次这样的查询。

你的目标是找到一个长度为 $n$ 的数组 $colors$，其中每个元素是 $1$ 到 $k$ 之间的整数，且 $colors[i] = colors[j]$ 当且仅当编号为 $i$ 和 $j$ 的小球颜色相同。

交互方式

第一行包含四个整数 $n, k, c, g$ $(1 \leq k \leq n \leq 10^{4})$，分别表示小球数量、颜色数量、最大查询次数和子任务编号。$c$ 的限制详见数据范围与提示。

你可以进行不超过 $c$ 次查询。要进行一次查询，输出一行包含数字 $1$ 和 $index$ $(1 \leq index \leq n)$，表示你想查看的小球位置。随后，输出换行符并刷新缓冲区。只有在完成这些操作后，你才能读取响应结果。

当你确定答案时，输出数字 $2$ 以及长度为 $n$ 的数组 $colors$，其中每个元素为 $1$ 到 $k$ 之间的整数。随后，输出换行符，刷新缓冲区，并终止程序。

样例

输入

5 3 100 0

0

0

1

1

0

2

3

输出

1 1

1 2

1 3

1 4

1 5

1 1

1 3

2 1 2 1 2 3

假设 $n=5$，$k=3$，$c=100$，隐藏颜色数组为 $[2, 1, 2, 1, 3]$。

如果你查看第 $1$ 个小球，得到的响应值为 $1$。如果你再次查看第 $1$ 个小球，响应值为 $2$。接着查看第 $2$ 个小球，响应值为 $1$。然后查看第 $3$ 个小球，响应值为 $3$。查看第 $4$ 个小球，响应值为 $2$。最后查看第 $5$ 个小球，响应值为 $1$。

之后，你可以返回数组 $[2, 3, 2, 3, 1]$。这个答案是正确的。

数据范围与提示

详细子任务附加限制及分值如下表所示：

对于最后一个子任务：

• 使用不超过 $4 \cdot 10^{6}$ 次查询，得 $7$ 分；
• 使用不超过 $10^{6}$ 次查询，得 $17$ 分；
• 使用不超过 $6 \cdot 10^{5}$ 次查询，得 $32$ 分；
• 使用不超过 $3 \cdot 10^{5}$ 次查询，得 $47$ 分。