#215619. [KTSC 2026] 排序 / Sorting

提交注意事项：

1. 不要引入头文件。
2. 在文件头加入

   #include <vector>
   #include <array>
   std::vector<int> sorting(int);
   std::vector<int> ask_question(std::vector<std::array<int, 2>>);
   

3. 使用 提交。

这是一道交互题。本题中，交互库是自适应的。

Alice 和 Bob 在玩游戏。Alice 有 个物品，编号 。第 个物品的价值是非负整数 。

Alice 知道所有物品的价值，但是 Bob 只知道物品数量 ，以及所有物品的价值都是非负整数。Bob 的目标是将物品按价值不降地排序。换言之，Bob 需要找到一个 的排列 ，满足：

• 对任意 ，。

为此，Bob 可以向 Alice 提出 个询问。

用最少的询问次数帮助 Bob 达成目标。

实现细节

这是一道函数式交互题。你不必，也不应实现 main 函数。

你应当实现以下的函数：

vector<int> sorting(int N)

• ：物品数量。
• 返回一个数组 ，将物品编号按照价值不降地排序。若有多解，任意返回一个均可。
• 该函数被调用恰好一次。

你可以调用以下的函数：

vector<int> ask_question(vector<array<int, 2>> threads)

• 表示一次 Bob 对 Alice 的询问。
• threads：大小为 的二元组数组，描述树边。每个 threads 中的元素 表示一条树边 。
• threads 必须描述一棵树。
• 返回一个大小为 的整数数组 。若选择的最大独立集中包含 ，则 ；否则 。
  • 若有多解，Alice 会任意返回一个。注意，传入相同的 threads 数组在同一测试点中多次调用该函数，返回值可能不同。
• 每个测试点中，该函数最多可调用 次。

示例评分程序的输入格式如下：

• 第 行：
• 第 行：

提供的示例评分程序仅在输入 为 到 （含）之间的整数时才能保证正常运行。

示例评分程序按以下格式打印你的代码在 sorting 函数中返回的数组以及调用 ask_question 函数的次数：

• 第 行：假设 sorting 函数返回了一个长度为 的数组 ，
• 第 行：调用 ask_question 函数的次数，

请注意，示例评分程序可能与实际评测中使用的评分程序有所不同。

样例输入 1

6
5 3 3 0 8 1

样例输出 1

3 5 1 2 0 4
2

数据范围

• ；
• 是非负整数。注意，没有限制 的上界。
• 每个测试点中，最多可调用 次 ask_question。
• 交互库是自适应的。换言之， 不是固定的，可能会根据 ask_question 函数的调用情况改变。回答时，交互库保证存在一个数组 满足所有先前的 ask_question 函数的回答。
• 每个测试点中，交互库至多消耗 秒时间和 内存。

子任务

计分方式

子任务

若答案合法，得满分。

子任务

若答案错误，或者程序异常终止，得 分。

否则，令 为该子任务单个测试点内调用 ask_question 次数的最大值，并计算 ：

该子任务得 的分数。

样例

考虑 且代表 Alice 拥有的物品价值的数组 为 的情况。

评分程序最初调用以下函数：

sorting(6)

参赛者的代码可能会进行如下交互：

ask_question([[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]])
ask_question([[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]])

在第一次调用的情况下，如果 Alice 选择物品 ，价值总和为 ，这是最大值。因此，此调用返回 。

在第二次调用的情况下，Alice 在满足条件时可以选取的物品集合为 和 。因此，此调用返回 或 。

考虑以下交互：

ask_question([[0, 1], [2, 3], [4, 5]])
ask_question([[0, 1], [1, 2], [2, 3], [3, 0], [4, 5]])

在第一次调用的情况下，这不是一次有效的调用，因为 threads 数组的大小不是 。

在第二次调用的情况下，这不是一次有效的调用，因为给定的不是一棵树。

有两个满足条件的整数数组 ：

因此，该函数必须返回这两个数组之一。