背景

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' 操作，并终止程序。

输出格式

见交互说明

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$，且实际颜色数组为 $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 完成