题目背景

提交注意事项：

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

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

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 函数。

你应当实现以下的函数：

vector<int> sorting(int N)

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

你可以调用以下的函数：

vector<int> ask_question(vector<array<int, 2>> 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$

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

6
5 3 3 0 8 1

3 5 1 2 0 4
2

提示

数据范围

• $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]$ 的情况。

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

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 选择物品 $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]$。

考虑以下交互：

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]$

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