CF1286C2 Madhouse (Hard version)

本题与简单版本的区别仅在于对所有答案总长度的限制。 这是一个交互题。 Venya 参加了一个疯人院之旅，护工们和病人们玩如下的游戏。护工们选择一个长度为 $n$ 的字符串 $s$，该字符串仅由小写英文字母组成。玩家可以进行两种类型的查询： - ? l r —— 询问 $s[l..r]$ 的所有子串。所有子串将以随机顺序返回，并且每个子串中的所有字符也会被随机打乱。 - ! s —— 猜测护工们选定的字符串。该查询只能进行一次，之后游戏结束。如果猜测正确，玩家获胜，否则失败。 玩家最多只能进行 $3$ 次第一种类型的查询。 为了方便护工们，还有一个额外限制：所有第一种类型查询返回的子串总数不得超过 $\left\lceil 0.777(n+1)^2 \right\rceil$（$\lceil x \rceil$ 表示对 $x$ 向上取整）。 Venya 请你编写一个程序，通过与护工们的程序交互，并按照游戏规则猜出字符串。 你的程序在使用第二种类型的查询猜测字符串后应立即终止。如果猜测错误，或违反了游戏规则，将会收到 Wrong answer 的判定。 注意，每个测试用例中的字符串在游戏开始前已固定，游戏过程中不会改变，也就是说交互器是非自适应的。

第一行包含一个整数 $n$（$1 \le n \le 100$），表示被选中的字符串的长度。

你需要通过读取 $n$ 开始交互。 若要查询从 $l$ 到 $r$（$1 \le l \le r \le n$）的子串，应在单独一行输出： ? l r 随后将返回 $s[l..r]$ 的所有子串，顺序随机，每个子串中的字符也会被随机打乱。 如果你的查询不合法，或进行了超过 $3$ 次第一种类型的查询，或所有查询返回的子串总数超过 $\left\lceil 0.777(n+1)^2 \right\rceil$，你将收到 Wrong answer 的判定。 若要猜测字符串 $s$，应在单独一行输出： ! s 每次输出查询后，别忘了刷新输出缓冲区，否则会收到 Idleness limit exceeded 的判定。刷新方法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请查阅相关文档。 如果你收到 -（短横线）作为任何查询的回复，需立即以退出码 0 终止程序（例如调用 exit(0)）。这表示交互协议出现错误。如果不这样做，可能会收到任意失败判定。 Hack 格式 如需 Hack 某个解法，使用如下格式： 第一行输入一个整数 $n$（$1 \le n \le 100$），第二行输入字符串 $s$。

由 ChatGPT 4.1 翻译