题目类型说明

这是一道提交函数题 / 交互式思维题 / 评分题。

你不需要编写 main 函数。系统维护一个长度为 N 的隐藏数组 A，你只能通过比较两个数对元素和的大小来获取信息，目标是在尽量少的查询次数内，将所有无序下标对 (i, j)（其中 0 <= i <= j < N）按 A_i + A_j 非降序排列。

---

题目描述

系统中有一个整数数组：

A_0, A_1, ..., A_{N-1}

你只知道数组长度 N，并不知道其中元素的具体值。

你需要输出一个序列：

(i_0, j_0), (i_1, j_1), ..., (i_{N(N+1)/2-1}, j_{N(N+1)/2-1})

满足：

1. 对于任意 0 <= i <= j < N，该数对在序列中恰好出现一次；
2. 序列按对应和非降序排列，即对于所有合法的 k >= 1，有：

$$A_{i_{k-1}} + A_{j_{k-1}} \le A_{i_k} + A_{j_k}$$

你不能直接访问数组 A，只能通过查询函数比较两个数对和的大小。

---

你需要实现的函数

std::vector<std::pair<int, int>> solve(int n);

该函数只会被调用一次，参数 n 为数组长度。

你可以重复调用下面的比较函数：

bool cmp(int a, int b, int c, int d);

其返回值含义为：

• 若 A_a + A_b < A_c + A_d，返回 true；
• 否则返回 false。

要求所有查询参数均满足：

0 <= a, b, c, d < N

---

提交要求

你需要提交 sqsort.cpp，其中：

• 必须包含 solve 函数；
• 必须包含头文件：

#include "sqsort.h"

• 不能包含 main 函数；
• 不能读写标准输入输出。

---

本地测试

题目提供了 sqsort.h 和 Lgrader.cpp。你可以将它们与自己的代码一同编译。

本地评测器启动后会先读入：

• 一个整数 N
• 一个长度为 N 的数组 A

随后调用你的 solve(n)，并响应所有 cmp 查询。最终会输出：

• 你使用的查询总次数，或
• “结果未正确排序”等错误信息

评测器保证正式评测时的行为与 Lgrader.cpp 等价，且不会根据你的查询进行自适应构造。

---

数据范围

• 100 <= N <= 2000

---

评分方式

每个测试点单独计分。

设你总共使用了 Q 次查询，则：

• 如果 Q > 5 × 10^7，或返回的序列不合法，则该测试点得 0 分；
• 否则，该测试点得分为：

$$\min\left(1,\left(\frac{2N^2+1}{Q+1}\right)^{1.25}\right)\times P$$

其中 P 为该测试点的满分。

也就是说，查询次数越少，得分越高。

---

样例交互说明

假设隐藏数组为：

A = {5, 1, 3}

评测过程可能如下：

步骤	选手程序操作	评测器响应
1	solve(3)
2	cmp(0, 1, 0, 0)	true
3	cmp(0, 2, 0, 0)
4	cmp(0, 2, 0, 1)	false
5	cmp(1, 2, 1, 1)
6	cmp(2, 2, 1, 2)
7	cmp(1, 1, 0, 1)	true
8	cmp(1, 2, 0, 1)
9	cmp(2, 2, 0, 1)	false
10	cmp(2, 2, 0, 2)	true
11	返回 [(1,1),(1,2),(0,1),(2,2),(0,2),(0,0)]

此时：

A_1+A_1 <= A_1+A_2 <= A_0+A_1 <= A_2+A_2 <= A_0+A_2 <= A_0+A_0

因此返回序列正确，且共使用了 9 次查询。