题目描述

Matthew 有 $2N$ 只鞋子，编号为 $1$ 到 $2N$。它们两两组成 $N$ 对。

不过这些鞋子并没有按配对摆放，而是被随机打乱了。你的目标是找出所有配对，但 Matthew 只愿意回答如下问题：

• 在鞋子集合 $V$ 中，是否至少存在一对完整的鞋子？

Matthew 很容易疲劳，因此你的目标是尽量减少提问次数。

你的程序会在每个测试上被评测 $T = 25$ 次，最终得分将根据每次评测所使用提问次数的平均值计算。

实现细节

你需要实现如下函数：

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

该函数在每个测试中会被调用 $T$ 次，参数 n 表示鞋子对数。

函数应返回一个由若干二元组构成的向量，每个二元组表示一对鞋子的编号。向量中各对的顺序、以及每对中两个数的顺序都无关紧要。

评测程序提供如下函数：

bool pairInSet(const std::vector<int> &v);

你的程序可以调用它任意多次。传入参数 v 表示你要询问的鞋子编号集合，其中元素必须互不相同，且都在 $1$ 到 $2N$ 之间。

• 若集合中至少包含一对完整鞋子，则该函数返回 true；
• 否则返回 false。

该函数的时间复杂度为 $O(SZ)$，其中 $SZ$ 为向量长度。

你的程序应当：

• 实现函数 guessPairs；
• 不要包含 main 函数；
• 不要从标准输入读取，也不要向标准输出写入；
• 必须通过预处理指令包含头文件：

#include "shoes.h"

只要满足以上要求，你可以自由添加辅助函数、变量、常量等内容。

数据范围

• $T = 25$
• $N = 5000$
• 对任意鞋子编号 $a_i$，有 $1 \le a_i \le 2N$
• 所有鞋子均被随机打乱
  （在第一个子任务中，左鞋与右鞋分别独立打乱）

子任务与评分

在某个子任务中，你获得的该子任务分值比例取决于你在每个子测试中平均提问次数 $Q$，以及该子任务给定的常数 $t1, t2$。

当 $Q \le t2$ 时：

$$\text{score} = \min\left(0.3 + 0.7\left(\frac{t2 - Q}{t2 - t1}\right)^{1.5},\ 1\right)$$

否则：

$$\text{score} = \max\left(0.3\left(\frac{t2}{Q}\right)^{0.75},\ 0.05\right)$$

子任务	分值	额外限制	评分常数
1	10	编号 $1 \dots N$ 的鞋子都是左鞋，编号 $N+1 \dots 2N$ 的鞋子都是右鞋。每一对都恰好由一只左鞋和一只右鞋组成。	$t1 = 54510$, $t2 = 64000$
2	90	无	$t1 = 59650$, $t2 = 64000$

本地测试

题目提供了文件 Lgrader.cpp 用于本地测试。要进行本地测试，你需要在代码中加入：

#include "Lgrader.cpp"

本地评测输入格式如下：

• 第一行输入两个整数 $N$ 和 $T$；
• 接下来共有 $T$ 组测试，每组给出 $N$ 对整数，表示每一对鞋子的编号。

如果你的程序对每组测试都成功找出了正确的配对，最后会输出你使用的平均提问次数。