题目来源

本题原题为函数式交互题。Hydro OJ 版本采用函数式 Grader 评测：选手只需要实现指定函数，不需要也不能编写 main 函数。

为了避免 Hydro 中使用 SPJ/partial verdict 时可能出现的 PE 或 RE，本版本不使用 SPJ。评测端 Grader 会自行判断答案和询问次数，正确时输出 1，错误时输出 0，再由默认比较器判断。

题目描述

你正在玩一个由四个按钮控制的电子游戏，四个按钮分别记为：

A, B, X, Y

游戏中存在一个秘密按钮序列 $S$。你不知道 $S$ 的内容，但知道它的长度为 $N$。

保证 $S$ 的每个字符都是 A、B、X、Y 中的一个，并且 $S$ 的第一个字符不会在 $S$ 的其他位置再次出现。

例如：

• ABXYY 可以作为秘密序列；
• XYYAA 可以作为秘密序列；
• AAAAA 不可以，因为第一个字符 A 在后面又出现了；
• BXYBX 不可以，因为第一个字符 B 在后面又出现了。

你可以进行若干次“连击询问”。一次询问中，你给出一个长度不超过 $4N$ 的字符串 $p$，其中每个字符也必须是 A、B、X、Y 中的一个。

评测器会返回：

$S$ 的前缀中，作为 $p$ 的连续子串出现的最长长度。

也就是说，返回最大的整数 $k$，满足 $S$ 的前 $k$ 个字符构成的字符串是 $p$ 的某个连续子串。空串总是可以出现，因此返回值可能为 $0$。

你的任务是通过尽量少的询问确定整个秘密序列 $S$。

实现要求

你需要提交一个 C++ 源文件，实现如下函数：

#include "combo.h"
#include <string>

std::string guess_sequence(int N);

其中：

• N 是秘密序列 $S$ 的长度；
• 该函数会在每个测试点中被调用恰好一次；
• 函数应返回你确定的秘密序列 $S$。

你可以调用评测器提供的函数：

int press(std::string p);

其中：

• p 是本次连击询问的字符串；
• 0 <= |p| <= 4N；
• p 中每个字符必须是 A、B、X、Y 之一；
• 每个测试点中调用次数不能超过 8000；
• 函数返回 $S$ 的某个前缀作为 p 的连续子串出现的最大长度。

如果你违反上述限制，或者最终返回的字符串不是 $S$，该测试点会判为错误。

Hydro 版本评分规则

本 Hydro 版本采用满分限制：

• 对于 $N=3$ 的测试点，只要求正确猜出 $S$；
• 对于其他测试点，需要正确猜出 $S$，并且 press 调用次数不超过 $N+2$。

这对应原官方题目中的满分标准。原官方的部分分评分方式没有在本 Hydro 版本中保留，以避免 SPJ 兼容问题。

输入输出格式

选手程序不需要读写标准输入输出。

评测端会从测试数据中读入秘密序列 $S$，然后调用你的 guess_sequence(N)。你只需要通过函数返回答案。

请不要在程序中输出调试信息，否则会影响评测结果。

本地测试

配置包中 download/ 目录提供了本地测试文件：

combo.h
Lgrader.cpp
combo.cpp

你可以把自己的提交文件与 Lgrader.cpp 放在同一目录下编译，例如：

g++ -std=c++17 -O2 your_solution.cpp Lgrader.cpp -o combo

本地测试时，标准输入只包含一行秘密序列 $S$。

例如：

ABXYY

如果本地 Grader 判断正确，会输出类似：

Accepted: 7

其中数字表示调用 press 的次数。

样例说明

假设秘密序列为：

ABXYY

若调用：

press("XXYYABYABXAY")

字符串 ABX 是 S 的前缀，且作为连续子串出现在询问串中；但 ABXY 没有作为连续子串出现，因此返回值为 3。

若调用：

press("ABXYYABXYY")

整个 ABXYY 都作为连续子串出现，因此返回值为 5。

若调用：

press("BXYY")

没有任何非空前缀作为连续子串出现，因此返回值为 0。

最终 guess_sequence(5) 应返回：

ABXYY

数据范围

• $1 \le N \le 2000$；
• $S$ 只包含字符 A、B、X、Y；
• $S$ 的第一个字符不会在其他位置出现；
• 每次询问串长度不超过 $4N$；
• 每个测试点调用 press 的次数不超过 8000。

@下发文件