AdditionalFile5485.zip

#5485. 「COI 2022」Mađioničar

标签: 交互 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

译自 COI 2022 T1「Mađioničar」

你可能听说过，马尔纳先生在业余时间会表演魔术。他最近在著名电视节目《Penn & Teller: Fool Us》中的亮相轰动了世界。他自称「神奇的马尔纳先生」，完成了一项令人难以置信的心理魔术，让所有人都为之倾倒。

他首先从观众中邀请了一位热情的志愿者，并请他们想一个由 $N$ 个字母组成的任意字符串。接着，他开始为观众表演，期间偶尔瞥一眼志愿者，最后他宣布：「你心中所想字符串的最长子回文串的长度为 $L'$」。在志愿者确认这完全正确后，全场观众都惊呆了。

然而，细心的观众和马尔纳先生的密友们怀疑，这并非读心术，而是一种巧妙的措辞选择，再结合对面部表情的出色解读，从而获得了足够的信息来完成这个魔术。

虽然马尔纳先生看起来只是在随意表演，但他会时不时地提到某个数字区间 $[l, r]$（其中 $1 \leq l \leq r \leq N$），并迅速地看一下志愿者。有传言说，他仅凭志愿者的面部表情，就能判断出其字符串中从第 $l$ 个到第 $r$ 个字母组成的子串（包含端点）是否为回文串。

你需要编写一个程序来证实，如果传言属实，马尔纳先生确实能够收集到足够的信息，以确定志愿者所选秘密字符串的最长子回文串。

交互方式

这是一道交互题。你的程序必须与一个由组织者制作的程序进行通信，该程序会模拟题目描述中志愿者的行为。

在交互开始前，你的程序应从标准输入读取一个整数 $N$，即秘密字符串的长度。

之后，你的程序可以通过向标准输出写入内容来发送查询请求。每个查询必须输出在新的一行，格式为 ? l r，其中 $1 \leq l \leq r \leq N$。每次写入查询后，你的程序都应刷新输出流，然后从标准输入读取回答。回答为 $1$ 表示子串 $[l, r]$ 是回文串，为 $0$ 则表示不是。你的程序最多可以进行 $200000$ 次此类查询。

当你的程序推断出最长子回文串的长度后，应向标准输出写入一行，格式为 ! L，其中 $L$ 是该长度。之后，你的程序应再次刷新输出流并正常终止执行。

注意：你可以从「文件」中下载能够正确处理交互（包括刷新输出）的示例代码。

样例

数据范围与提示

详细子任务附加限制及分值如下表所示：