当前没有测试数据。

题目描述

评测机隐藏了一个排列：

P_0, P_1, ..., P_{N-1}

它是集合 {1, 2, 3, ..., N} 的一个排列。你的任务是通过询问恢复这个排列。

你可以向评测机提出如下类型的问题：

是否可以用边长 P_A, P_B, P_C 构成一个面积大于 0 的三角形？

也就是说，你可以调用：

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

当且仅当边长 P_A, P_B, P_C 能构成正面积三角形时，它返回 true。

根据三角形不等式，这等价于同时满足：

[ P_A + P_B > P_C ] [ P_A + P_C > P_B ] [ P_B + P_C > P_A ]

请你通过尽量少的询问恢复整个排列。

---

实现要求

你需要实现如下函数：

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

其中：

• N：排列长度

函数会在每个子测试中被调用一次，你需要返回隐藏排列本身。

为了获得排列信息，你可以调用评测机提供的函数：

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

其中 A, B, C 为下标。

---

约束条件

• N = 1000
• T = 1000

其中 T 表示一个测试中会调用 solve 的次数。

---

子任务

本题只有一个子任务：

子任务	分值	描述
1	100	单个测试，T = 1000，每次隐藏排列均从所有 N = 1000 的排列中均匀随机生成

---

评分方式

设：

• Q_contestant：你的程序在该测试中，单次调用 solve 所使用询问次数的平均值
• Q_target = 8770

则本题得分为：

• 若 Q_contestant > 2 * 10^6，得分为 0
• 若 Q_contestant <= Q_target，得分为 100
• 否则按照原题给定的分段函数计算得分

也就是说，这是一道交互 + 评分题。
不仅要求恢复出正确排列，还要求尽量减少询问次数。

---

样例交互

下面给出原题中的一组样例交互过程。
在这个样例中，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

最后返回：

{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

最后返回：

{4, 2, 1, 3}

---

本地评测器

输入格式

• 第 1 行：三个整数 T, N, R
  • T：子测试数量
  • N：排列大小
  • R：运行模式

如果 R = 1：

• 本地评测器会随机生成排列
• 第 2 行应额外输入一个整数 S，作为随机种子

如果 R = 2：

• 接下来第 2 行到第 1 + T 行，每行给出一个 {1, 2, ..., N} 的排列

输出格式

• 如果所有排列都恢复正确，则输出平均询问次数
• 否则输出错误信息