「HOI R1」杂交选种

$\clubsuit$ 星球盛产“代马”，其优越的速度与耗能使得它风靡整个银河系。可小 $\iiint$ 并不满足于此，他想培育出更好的“代马”，并取代掉还在用传统能源的落后四足兽。于是，他开始研究基因技术…… **本题仅支持 C++ 语言提交。** **由于技术限制，请勿使用 C++14 (GCC 9) 语言提交，否则将会得到 Compile Error 的结果。** 你的代码中需如下进行 `query` 和 `cross` 函数的声明： ```cpp char query(int k); void cross(int i, int j); ``` 调用 $10^6$ 次 `query` 与 `cross` 函数的时间不超过 50 毫秒，除这两个函数所占用的时间外，交互库运行所占用的时间不超过 100 毫秒。

#### 【形式化题意】 **这是一道交互题。** 定义 **基因** 为一个字符，其内容为 $\verb!A!$ 或 $\verb!a!$。定义 **基因型** 为由两个基因组成，且大写字母在小写字母之前的字符串。也即 $\{\verb!aa!,\verb!Aa!,\verb!AA!\}$ 中的一种。一个基因型的 **表现** 如下： - 若基因型中含有 $\verb!A!$，则表现为 $\verb!A!$。 - 否则，表现为 $\verb!a!$。 两个基因型可以相互 **杂交**，其定义如下： - 在两个基因型中各均匀随机取一个基因，并将两个基因组合成基因型作为结果输出。 小 $\iiint$ 有 $n$ 个基因型，编号为 $1,2,\cdots,n$。每次询问可以给交互库两个不同的编号 $i,j$。若当前是第 $k$ 次杂交，交互库会新建一个编号为 $n+k$ 的基因型，其基因型为 $i,j$ 杂交后的结果。 你可以在时限范围内任意次查询编号为 $x$ 的种子的表现。你需要在 $4.5\times10^5$ 次杂交内，求出初始给定的 $n$ 个基因型。 ### 实现细节 **你不需要，也不应该实现主函数。** 你需要实现下面的函数： ```cpp vector<string> guess(int n) ``` - $n$ 表示初始基因型个数。 - 该函数应当返回一个长度恰好为 $n$ 的数组，数组中的每一个元素是一个长度为二的字符串，表示你所求出的基因型。**你需要保证大写字母在小写字母的前面**。 - 对于每个测试点，该函数被恰好调用一次。 该函数可调用以下函数： ```cpp char query(int k) ``` - $k$ 表示你要查询的基因型的编号。**你需要保证这个编号对应的基因型存在**。 - 该函数将返回该基因型的表现。 - 该函数可以在时限内被调用任意次。 ```cpp void cross(int i, int j) ``` - $i,j$ 代表你要杂交的两个基因的编号。**你需要保证 $i\not=j$ 且对应的基因型存在**。 - 若是第 $k$ 次调用该函数，该函数会新建一个编号为 $n+k$ 的基因型，其基因型为 $i,j$ 杂交后的结果。保证杂交过程为均匀随机。 - 你最多可以调用该函数 $4.5\times10^5$ 次。 - 评测程序不是适应性的。也就是说，所有初始元素的基因型在 `guess` 函数被调用前已经确定。

#### 【交互示例】 以下为 $n=2$，基因型为 $\{\verb!Aa!,\verb!AA!\}$ 时一种可能的交互过程。 |选手程序|交互库| |:-:|:-:| ||`guess(2)`| |`cross(1,2)`|| ||$\{\verb!Aa!,\verb!AA!,\verb!Aa!\}$| |`cross(1,3)`|| ||$\{\verb!Aa!,\verb!AA!,\verb!Aa!,\verb!aa!\}$| |`query(4)`|| ||$\verb!a!$| |$\{\verb!Aa!,\verb!AA!\}$|| ||`Ok,accepted.`| #### 【约束条件】 + $2\le n\le 2\times10^4$，$n$ 为偶数。 + 每次程序运行时将恰好调用一次 `guess()` 函数。 + 保证交互库是非自适应性的，即所有初始元素的基因型不在交互过程中发生改变。 #### 【子任务】 |Subtask|分值|$n\le$|特殊性质| |:-:|:-:|:-:|:-:| |$0$|$0$|$2$|无| |$1$|$5$|$2\times10^4$|保证不存在 $\verb!Aa!$| |$2$|$15$|$500$|无| |$3$|$20$|$2\times10^4$|保证至少存在一个 $\verb!aa!$| |$4$|$25$|$5\times10^3$|无| |$5$|$35$|$2\times10^4$|无| 对于所有数据，$2\le n\le 2\times10^4$，保证 $n$ 为偶数。 由于本题涉及概率与期望，如果你确定你的算法无误，可以尝试多交几发。