AdditionalFile5623.zip

#5623. 「KTSC 2026 R2」排序

标签: 传统 | 时间限制: 5000 ms | 内存限制: 2048 MiB |

注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "sorting.h"。

题目描述

题目译自 2026년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「정렬하기」

艾丽丝和鲍勃正在玩一个游戏。艾丽丝有 $N$ 个物品，编号为 $0$ 到 $N-1$。每个物品 $i$ 的价值是一个非负整数 $A[i]$。

艾丽丝知道所有物品的价值，但鲍勃只知道物品的数量 $N$ 以及每个物品的价值都是非负整数。鲍勃的目标是将这些物品按价值不减的顺序进行排序。也就是说，鲍勃需要找到一个长度为 $N$ 的整数数组 $P$，满足以下条件：

• $P$ 中的每个元素互不相同。
• $P$ 的所有元素都在 $0$ 到 $N-1$ 之间。
• 对于所有满足 $0 \leq i \leq N-2$ 的整数 $i$，均有 $A[P[i]] \leq A[P[i+1]]$。

为此，鲍勃可以向艾丽丝最多进行 $10000$ 次询问。每次询问的过程如下：

1. 鲍勃安装 $N-1$ 根细绳，每根细绳连接两个不同的物品。此时，所有物品必须通过细绳连通，使得任意两个物品之间都可以沿着细绳互相到达（即构成一棵树）。

2. 艾丽丝根据以下规则选择 $0$ 个或多个物品：

   • 不能同时选择由细绳直接连接的两个物品。
   • 在满足上述条件的前提下，所选物品的价值总和必须尽可能大。

   如果满足条件的物品组合有多种，艾丽丝会从中随机选择一种，并告知鲍勃。

3. 艾丽丝将选中的物品告知鲍勃，并拆除所有的细绳。

你需要帮助鲍勃通过尽可能少的询问次数来赢得游戏。

实现细节

你需要实现以下函数：

vector<int> sorting(int N)

• $N$：游戏中使用的物品数量。
• 该函数应返回一个物品编号数组 $P$，其中的编号按价值不减的顺序排列。如果满足条件的数组 $P$ 不唯一，可以返回其中任何一个。
• 该函数仅会被调用一次。

该函数可以调用以下函数：

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

• 表示艾丽丝和鲍勃进行一次询问过程。
• threads：一个大小为 $N-1$ 的数组，表示由细绳直接连接的物品对。对于 threads 中的每个元素 $[a, b]$，表示在物品 $a$ 和物品 $b$ 之间安装一根细绳。
• 按照 threads 中指明的方式连接物品后，任意两个物品之间必须能通过细绳连通。
• 该函数返回一个长度为 $N$ 的整数数组 $C$。对于每个物品 $i$，如果艾丽丝在本次询问中选择了物品 $i$，则 $C[i]=1$；否则 $C[i]=0$ $(0 \leq i \leq N-1)$。
• 如果艾丽丝在本次询问中面对满足条件的物品组合不唯一的情况，评测程序会选择并返回其中一种数组 $C$。请注意，在同一个测试用例中，使用相同的 threads 数组多次调用 ask_question 可能会返回不同的数组。
• 在单个测试用例中，该函数最多可调用 $10000$ 次。

样例

假设 $N=6$ 且艾丽丝拥有的物品价值数组 $A$ 为 $[5, 3, 3, 0, 8, 1]$。

评测程序最初调用如下函数：

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}})

对于第一次调用，如果艾丽丝选择物品 $0, 2, 4$，则价值总和为 $5+3+8=16$，达到最大值。因此，该调用返回 $[1, 0, 1, 0, 1, 0]$。

对于第二次调用，艾丽丝在满足条件的前提下可以选择的物品集合有 $\{1, 2, 4, 5\}$ 和 $\{1, 2, 3, 4, 5\}$。因此，该调用会返回 $[0, 1, 1, 0, 1, 1]$ 或 $[0, 1, 1, 1, 1, 1]$ 中的一个。

考虑以下交互：

ask_question({{0, 1}, {2, 3}, {4, 5}})
ask_question({{0, 1}, {1, 2}, {2, 3}, {3, 0}, {4, 5}})

对于第一次调用，由于 threads 数组的大小不是 $N-1$，因此不是有效的调用。 对于第二次调用，由于无法沿着细绳从物品 $0$ 移动到物品 $4$，因此不是有效的调用。

满足条件的整数数组 $P$ 有以下两种：

• $[3, 5, 1, 2, 0, 4]$
• $[3, 5, 2, 1, 0, 4]$

因此，函数应返回这两个数组中的一个。

数据范围与提示

对于所有输入数据，满足：

• $5 \leq N \leq 1000$
• $A[i]$ 是非负整数。请注意，题目并未给出 $A[i]$ 的上限（$0 \leq i \leq N-1$）。
• ask_question 函数在单个测试用例中最多可调用 $10000$ 次。
• 在本题中，评测程序是自适应的（adaptive）。这意味着数组 $A$ 并不是固定的，可能会根据 ask_question 函数的调用情况而改变。评测程序保证每次给出回答时，至少存在一个数组 $A$ 与之前所有 ask_question 调用的结果相一致。
• 对于所有测试用例，可以假设评测程序在处理 ask_question 调用时，消耗的时间在 $2$ 秒以内，使用的内存不超过 $16 \text{ MiB}$。

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$7$	$N=5$
$2$	$8$	$N \leq 100$
$3$	$10$	满足 $0 \leq i < N$ 且 $A[i] > 0$ 的 $i$ 最多只有一个。
$4$	$30$	对于所有满足 $0 \leq i < \frac{N}{2}$ 的整数 $i$，均有 $A[i]=0$。
$5$	$45$	无附加限制

子任务 1 和 2：

如果 sorting 函数的返回值正确，则获得该子任务 $100\%$ 的分数。

子任务 3, 4, 5：

选手在这些子任务中获得的分数计算如下：

如果程序异常终止，或者 sorting 函数的返回值不正确，则得 $0$ 分。

否则，该子任务的分数将按以下方式计算：

设 $Q_{\max}$ 为该子任务中执行一次 sorting 函数时调用 ask_question 函数的最大次数。 根据 $Q_{\max}$ 定义 $X$ 如下：

条件	$X$
$10000 < Q_{\max}$	$0$
$80 < Q_{\max} \leq 10000$	$90 - 35 \log_{10}\left(\frac{Q_{\max}}{80}\right)$
$70 < Q_{\max} \leq 80$	$170 - Q_{\max}$
$Q_{\max} \leq 70$	$100$

选手将获得该子任务分值的 $X\%$。

示例评测程序

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

• 第一行包含一个整数 $N$。
• 第二行包含 $A[0] \ A[1] \ \ldots \ A[N-1]$。

提供的示例评测程序仅在输入的 $A[i]$ 为 $0$ 到 $10^9$ 之间的整数时才能保证正常运行。

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

• 第一行：假设 sorting 函数返回了长度为 $M$ 的数组 $P$，则输出 $P[0] \ P[1] \ \ldots \ P[M-1]$。
• 第二行：调用 ask_question 函数的次数 $Q$。

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