P15587 [KTSC 2026] 排序 / Sorting

提交注意事项： 1. **不要**引入头文件。 2. 在文件头加入 ```cpp #include #include std::vector sorting(int); std::vector ask_question(std::vector); ``` 3. 使用 $\texttt{C++\,\red{20/23}}$ 提交。

**这是一道交互题。本题中，交互库是自适应的。** Alice 和 Bob 在玩游戏。Alice 有 $N$ 个物品，编号 $0\sim N-1$。第 $i$ 个物品的价值是非负整数 $A[i]$。 Alice 知道所有物品的价值，但是 Bob 只知道物品数量 $N$，以及所有物品的价值都是非负整数。Bob 的目标是将物品按价值不降地排序。换言之，Bob 需要找到一个 $0\sim N-1$ 的排列 $P$，满足： - 对任意 $0\le i\le N-2$，$A[P[i]]\le A[P[i+1]]$。 为此，Bob 可以向 Alice 提出 $10\, 000$ 个询问。 >**询问** > >1. Bob 给定一棵 $N$ 个节点的树，其中节点编号 $0\sim N-1$。点 $i$ 的点权为 $A[i]$。 >2. Alice 任选一个这棵树的最大独立集（可以为空），并返回给 Bob。随后 Alice 将这棵树清除。 > - 换言之，Alice 选择一个点集 $V\subseteq \{0,1,\ldots,N-1\}$（可以是空集），满足 $V$ 中任意两点没有边相连，且 $\sum_{v\in V} A[v]$ 最大。 > > 若有多个符合条件的点集，Alice 将任意选择一个。 用最少的询问次数帮助 Bob 达成目标。 ### 实现细节 **这是一道函数式交互题**。你不必，也不应实现 `main` 函数。 你应当实现以下的函数： ```cpp vector sorting(int N) ``` - $N$：物品数量。 - 返回一个数组 $P$，将物品编号按照价值不降地排序。若有多解，任意返回一个均可。 - 该函数被调用恰好一次。 你可以调用以下的函数： ```cpp vector ask_question(vector threads) ``` - 表示一次 Bob 对 Alice 的询问。 - `threads`：大小为 $N-1$ 的二元组数组，描述树边。每个 `threads` 中的元素 $[a,b]$ 表示一条树边 $(a,b)$。 - `threads` 必须描述一棵树。 - 返回一个大小为 $N$ 的整数数组 $C$。若选择的最大独立集中包含 $i$，则 $C[i]=1$；否则 $C[i]=0$。 - 若有多解，Alice 会任意返回一个。注意，传入相同的 `threads` 数组在同一测试点中多次调用该函数，返回值可能不同。 - 每个测试点中，该函数最多可调用 $10\,000$ 次。

示例评分程序的输入格式如下： * 第 $1$ 行：$N$ * 第 $2$ 行：$A[0] A[1] \dots A[N - 1]$ 提供的示例评分程序仅在输入 $A[i]$ 为 $0$ 到 $10^9$（含）之间的整数时才能保证正常运行。

示例评分程序按以下格式打印你的代码在 sorting 函数中返回的数组以及调用 ask_question 函数的次数： * 第 $1$ 行：假设 sorting 函数返回了一个长度为 $M$ 的数组 $P$，$P[0] P[1] \dots P[M - 1]$ * 第 $2$ 行：调用 ask_question 函数的次数，$Q$ 请注意，示例评分程序可能与实际评测中使用的评分程序有所不同。

### 数据范围 - $5\le N\le 1\, 000$； - $A[i]$ 是非负整数。注意，没有限制 $A[i]$ 的上界。 - 每个测试点中，最多可调用 $10\,000$ 次 `ask_question`。 - 交互库是自适应的。换言之，$A$ 不是固定的，可能会根据 `ask_question` 函数的调用情况改变。回答时，交互库保证存在一个数组 $A$ 满足所有先前的 `ask_question` 函数的回答。 - 每个测试点中，交互库至多消耗 $2$ 秒时间和 $16\, \mathrm{MiB}$ 内存。 ### 子任务 | 编号 | 得分 | 限制 | | :-: | :-: | :- | | $1$ | $ 7$ | $N=5$ | | $2$ | $ 8$ | $N \le 100$ | | $3$ | $10$ | $\forall 0\le i\lt N$，至多存在一个使得 $A[i]\gt 0$ 的 $i$ | | $4$ | $30$ | $\forall 0\le i\lt \frac{N}{2}$，$A[i]=0$ | | $5$ | $45$ | 无额外限制 | ### 计分方式 #### 子任务 $1,2$ 若答案合法，得满分。 #### 子任务 $3,4,5$ 若答案错误，或者程序异常终止，得 $0$ 分。 否则，令 $Q_{\max}$ 为该子任务单个测试点内调用 `ask_question` 次数的最大值，并计算 $X$： | 条件 | $X=$ | | :- | :- | | $10\, 000 \lt Q_{\max}$ | $0$ | | $80 \lt Q_{\max}\le 10\, 000$ | $90 - 35\log_{10}\left(\frac{Q_{\max}}{80}\right)$ | | $70\lt Q_{\max}\le 80$ | $170-Q_{\max}$ | | $Q_{\max} \le 70$ | $100$ | 该子任务得 $X\%$ 的分数。 ### 样例 考虑 $N = 6$ 且代表 Alice 拥有的物品价值的数组 $A$ 为 $[5, 3, 3, 0, 8, 1]$ 的情况。 评分程序最初调用以下函数： ```cpp sorting(6) ``` 参赛者的代码可能会进行如下交互： ```cpp 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 选择物品 $0, 2, 4$，价值总和为 $5 + 3 + 8 = 16$，这是最大值。因此，此调用返回 $[1, 0, 1, 0, 1, 0]$。 在第二次调用的情况下，Alice 在满足条件时可以选取的物品集合为 $\{1, 2, 4, 5\}$ 和 $\{1, 2, 3, 4, 5\}$。因此，此调用返回 $[0, 1, 1, 0, 1, 1]$ 或 $[0, 1, 1, 1, 1, 1]$。 考虑以下交互： ```cpp ask_question([[0, 1], [2, 3], [4, 5]]) ask_question([[0, 1], [1, 2], [2, 3], [3, 0], [4, 5]]) ``` 在第一次调用的情况下，这不是一次有效的调用，因为 `threads` 数组的大小不是 $N - 1$。 在第二次调用的情况下，这不是一次有效的调用，因为给定的不是一棵树。 有两个满足条件的整数数组 $P$： * $[3, 5, 1, 2, 0, 4]$ * $[3, 5, 2, 1, 0, 4]$ 因此，该函数必须返回这两个数组之一。