P16376 [IATI 2026] Triangle
题目描述
国家委员会的新领导层，由 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` 函数：
```cpp
std::vector solve(int N);
```
- $N$：排列的长度。
对于每个测试点，该函数将被调用 $T$ 次 —— 每个子测试调用一次，每次的 $N$ 均相同，它需要返回该子测试中隐藏的排列。为此，你的程序可以调用查询函数 `query`：
```cpp
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)` | `false` |
| `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)` | `false` |
| `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 完成