题目描述

国家委员会的新领导层，由 A 组和 B 组的协调员代表，希望为选拔国家队而维持一套严格的题目大纲。为此，他们需要出一道几何题。而且 —— 目前所出的交互题数量低于标准。为了弥补 $\texttt{IOI}$ 选拔中的这一缺口，Sashka 决定出一道既交互又几何的题目。题目描述如下：

评审团已隐藏了一个 $\{1,2,3,\dots,N\}$ 的排列 $P_0,P_1,\dots,P_{N-1}$。你必须找出这个排列。为此，你可以向评审团提出如下询问：“以 $P_A,P_B,P_C$ 为边长，能否构成一个面积为正的三角形？”

注意，根据三角形不等式，我们已知这等价于：

$$P_A + P_B > P_C,\ P_A + P_C > P_B \quad \text{且} \quad P_B + P_C > P_A.$$

请编写一个程序 triangle，其中包含一个函数 solve，它将与评审程序一起编译，并通过提出上述类型的询问与之通信。在程序运行结束时，必须确定出该排列。

实现细节

你需要实现 solve 函数：

std::vector<int> solve(int N);

• $N$：排列的长度。

对于每个测试点，该函数将被调用 $T$ 次 —— 每个子测试调用一次，每次的 $N$ 均相同，它需要返回该子测试中隐藏的排列。为此，你的程序可以调用查询函数 query：

bool query(int A, int B, int C);

• $A$, $B$, $C$：表示边长 $P_A, P_B, P_C$ 的下标。

若存在以 $P_A,P_B,P_C$ 为边长且面积为正的三角形，函数返回 true，否则返回 false。

输入格式

输入格式：

• 第 $1$ 行：三个整数 $T$、$N$ 和 $R$ —— 子测试的数量、排列的大小以及运行模式。若 $R = 1$，本地评测机将生成均匀随机的排列，并期望在第 $2$ 行输入一个整数 —— $S$，用作其随机数生成器的种子。若 $R = 2$，则输入按如下继续：
• 第 $2$ 行到第 $(1+T)$ 行：$\{1,2,\dots,N\}$ 的排列。

输出格式

输出格式：

• 第 $1$ 行：若所有排列均已正确识别，则输出子测试的平均询问次数，否则输出错误信息。

提示

交互样例

在该交互样例中，$N=4$，$T=2$。

选手操作	评审操作
	solve(4)
query(0, 0, 0)	true
query(0, 1, 2)	false
query(0, 1, 3)
query(0, 2, 3)	true
query(1, 2, 3)	false
return {3, 1, 2, 4};
	solve(4)
query(0, 1, 2)	false
query(0, 1, 3)	true
query(0, 2, 3)	false
query(1, 2, 3)
return {4, 2, 1, 3};

数据范围

• $N = T = 1\,000$

子任务

子任务	分值	描述
$1$	$100$	该子任务包含一个测试点，其中 $T=1\,000$，且每个排列均从所有可能的排列中随机均匀采样，每个排列包含 $N=1\,000$ 个元素。

仅当某子任务的所有测试点均成功通过时，才能获得该子任务的分数。

评分规则

设 $Q_{\text{选手}}$ 为你的程序在单个测试点上单次 solve 调用的平均询问次数，并设 $Q_{\text{目标}}=8770$。则你在本题的得分将为：

$$\begin{cases} 0 & \text{若 } Q_{\text{选手}} > 2\times 10^6, \\ 100 & \text{若 } Q_{\text{选手}} \le Q_{\text{目标}}, \\ 100 \times \max\left(0.15,\; 1-\sqrt{1-\left(\dfrac{Q_{\text{目标}}}{Q_{\text{选手}}}\right)^{0.55}}\right) & \text{若 } Q_{\text{选手}} > Q_{\text{目标}}. \end{cases}$$

翻译由 DeepSeek V4 Pro 完成