P12635 [UOI 2020] Guess the Color

6-60s 256M

给定编号从 $1$ 到 $n$ 的 $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$），表示你要查看的球的位置。之后，你需要输出换行符并执行 'flush' 操作。只有在执行完这些操作后，你才能读取查询结果。 当你已经知道答案时，你需要输出数字 $2$ 和长度为 $n$ 的数组 $colors$，其中每个元素是 $1$ 到 $k$ 之间的整数。之后，你需要输出换行符，执行 'flush' 操作，并终止程序。

见交互说明

设 $n=5$，$k=3$，$c=100$，且实际颜色数组为 $a = [2\ 1\ 2\ 1\ 3]$。 如果你查询球 $1$，你会得到返回值 $1$。如果再次查询球 $1$，返回值将是 $2$。查询球 $2$ 时，返回值是 $1$。查询球 $3$ 时，返回值是 $3$。查询球 $4$ 时，返回值是 $2$。查询球 $5$ 时，返回值是 $1$。 之后，你可以返回数组 $[2\ 3\ 2\ 3\ 1]$。这个答案是正确的。 ### 评分标准 - （$7$ 分）$n \leq 10^4$；$k = n-1$；$c = 5 \cdot 10^4$；只有两个球同色，其余球颜色各不相同； - （$7$ 分）$n \leq 10^4$；$k = 2$；$c = 5 \cdot 10^4$； - （$10$ 分）$n \leq 500$；$k \leq n$；$c = 3 \cdot 10^5$； - （$14$ 分）$n \leq 10^4$；$k \leq 10$；$c = 3 \cdot 10^5$； - （$15$ 分）$n \leq 10^4$；$k \leq n$；$c = 2 \cdot 10^4$；每种颜色对应的球的数量互不相同，且每种颜色至少出现一次； - （最多 $47$ 分）$n \leq 10^4$；$k \leq n$；$c = 4 \cdot 10^6$： - $7$ 分：使用不超过 $4 \cdot 10^6$ 次查询； - $17$ 分：使用不超过 $10^6$ 次查询； - $32$ 分：使用不超过 $6 \cdot 10^5$ 次查询； - $47$ 分：使用不超过 $3 \cdot 10^5$ 次查询。 翻译由 DeepSeek V3 完成