题目描述
题目译自 Ukrainian Olympiads in Informatics 2020 Stage 4 Day1 T3. Вгадайте колір
有 n 个小球，编号从 1 到 n，每个小球有 1 种颜色，总共有 k 种不同颜色（1≤k≤n）。你需要通过查询确定每个小球的颜色归属，满足：数组 colors 中 colors[i]=colors[j] 当且仅当编号 i 和 j 的小球颜色相同（颜色取值范围为 1 到 k）。
查询规则如下：
- 每次查询需指定一个小球编号 index（1≤index≤n）；
- 查询响应为“当前已查看过的同色小球数量”（包含本次查询的小球）；
- 总查询次数不得超过 c 次（c 的限制见数据范围）。
交互方式
- 输入初始信息：第一行包含四个整数 n,k,c,g（1≤k≤n≤104），分别表示小球数量、颜色种类数、最大查询次数、子任务编号。
- 执行查询：每次输出一行
1 index，表示查询编号为 index 的小球；输出后需换行并刷新缓冲区，随后读取查询响应（一个整数）。
- 提交答案：确定结果后，输出一行
2 colors_1 colors_2 ... colors_n（每个 colorsi 满足 1≤colorsi≤k）；输出后换行并刷新缓冲区，程序终止。
样例
交互过程说明
假设隐藏颜色数组为 [2,1,2,1,3]（n=5,k=3,c=100），交互流程如下：
| 你的输出（查询/答案） |
系统响应（查询结果） |
说明 |
1 1 |
0（实际应为 1，样例输入可能存在笔误，以逻辑为准） |
首次查询小球 1，同色已查看数量为 1 |
1 2 |
0（实际应为 1） |
首次查询小球 2，同色已查看数量为 1 |
1 3 |
1（实际应为 2） |
第二次查询同色（与小球 1 同色），数量为 2 |
1 4 |
第二次查询同色（与小球 2 同色），数量为 2 |
1 5 |
0（实际应为 1） |
首次查询小球 5，同色已查看数量为 1 |
1 1 |
2 |
第三次查询小球 1，同色已查看数量为 3（含小球 1,3） |
1 3 |
3 |
第三次查询小球 3，同色已查看数量为 3 |
2 1 2 1 2 3 |
- |
提交答案，与隐藏数组的归属一致（颜色编号可映射，正确） |
样例输入（系统响应部分）
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
数据范围与提示
详细子任务附加限制及分值如下表所示：
| 子任务 |
分值 |
附加限制 |
| 1 |
7 |
n≤104；k=n−1；c=5⋅104；仅两个小球同色，其余颜色唯一 |
| 2 |
n≤104；k=2；c=5⋅104 |
| 3 |
10 |
n≤500；k≤n；c=3⋅105 |
| 4 |
14 |
n≤104；k≤10；c=3⋅105 |
| 5 |
15 |
n≤104；k≤n；c=2⋅104；每种颜色的小球数量不同且至少出现一次 |
| 6 |
47 |
n≤104；k≤n；c=4⋅106（按查询次数分级得分） |
子任务 6 得分规则
- 查询次数 ≤4⋅106：得 7 分；
- 查询次数 ≤1⋅106：得 17 分；
- 查询次数 ≤6⋅105：得 32 分；
- 查询次数 ≤3⋅105：得 47 分。
