基于比较的排序问题（交互式）

题目描述

有 $N$ 个元素，编号 $1, 2, \dots, N$，每一对元素之间的大小关系是确定的，关系具有反对称性，但不具有传递性。

注意：不存在两个元素大小相等的情况。

也就是说，元素的大小关系是 $N$ 个点与 $\frac{N \times (N-1)}{2}$ 条有向边构成的任意有向图。

然而，这是一道交互式试题，这些关系不能一次性得知，你必须通过不超过 $10000$ 次提问来获取信息，每次提问只能了解某两个元素之间的关系。

现在请你把这 $N$ 个元素排成一行，使得每个元素都小于右边与它相邻的元素。

你可以通过我们预设的 bool 函数 compare 来获得两个元素之间的大小关系。

例如，编号为 $a$ 和 $b$ 的两个元素，如果元素 $a$ 小于元素 $b$，则 compare(a,b) 返回 true，否则返回 false。

将 $N$ 个元素排好序后，把他们的编号以数组的形式输出，如果答案不唯一，则输出任意一个均可。

数据范围

$1 \le N \le 1000$

交互方式

你需要实现一个函数 solution(N, compare)，其中：

• N 是元素的数量
• compare(a, b) 是一个函数，返回 true 如果元素 a 小于元素 b，否则返回 false

你的函数应该返回一个数组，表示排好序的元素编号序列。

输入输出样例

示例 1

假设比较矩阵为：

compare(1,2) = true
compare(1,3) = false  
compare(2,3) = false

可能的输出：

[3, 1, 2]

或

[2, 3, 1]

示例 2

假设比较矩阵为：

compare(1,2) = true
compare(1,3) = true
compare(2,3) = false

可能的输出：

[1, 2, 3]

或

[1, 3, 2]

限制条件

1. 你需要使用 compare 函数来获取元素间的关系
2. 调用 compare 的次数不能超过 $10000$ 次
3. 大小关系满足反对称性：compare(a,b) 和 compare(b,a) 有且仅有一个为 true
4. 大小关系不一定满足传递性：即使 compare(a,b) 和 compare(b,c) 都为 true，compare(a,c) 也可能为 false

提示

1. 由于关系不具有传递性，不能直接使用传统的排序算法（如快速排序、归并排序等）
2. 一个有效的方法是使用插入排序的思想，逐个将元素插入到已排序的序列中
3. 对于每个新元素，通过二分查找找到它的合适位置
4. 这样的算法在最坏情况下需要 $O(N^2)$ 次比较，对于 $N=1000$，最多需要 $1000000$ 次比较，超过了 $10000$ 的限制
5. 实际上，插入排序平均需要约 $\frac{N^2}{4}$ 次比较，仍然会超限
6. 需要考虑更高效的算法或者优化比较次数