[COI 2024] Koreografija

Jura：Tvrtko，昨天的演出怎么样？ Tvrtko：非常棒。最精彩的部分是当 $1000$ 名舞者从左到右排列并开始表演时，那个编舞。他们每个人的服装上都写有一个 $1$ 到 $1000$ 之间的数字，并且这些数字都是不同的。但我不得不说，当我看到他们排成一行时，我不喜欢他们的顺序。 Jura：你是什么意思？ Tvrtko：我在队伍中看到了一些连续的舞者间隔，并计算了有多少对舞者是这样的：较低位置的舞者编号高于较高位置的舞者编号。我喜欢这样的对数是奇数的情况。 Jura：哦，Tvrtko，你得看大局。我会处理的。但告诉我，他们的编号顺序是怎样的？ Tvrtko：嗯……我已经忘了。但我可以告诉你对于每个连续的舞者间隔，我是否喜欢。 Jura：就这样吧。我们别无选择，只能尝试根据这个来确定他们的编号。 ## Input 这是一个交互任务。你的程序需要与组织者提供的程序建立对话，以响应所提出的问题。 你的程序可以通过向标准输出写入来发送查询。每个查询应单独打印在一行上，并应采用 `? a b` 的形式，其中 $a$ 和 $b$ 是满足 $1 \leq a \leq b \leq 1000$ 的正整数。数字 $a$ 和 $b$ 表示所观察区间的舞者位置。 在输出每个查询后，你的程序应刷新输出，并从标准输入读取对查询的响应——一个在集合 $\{0,1\}$ 的数字，表示 Tvrtko 对该区间的看法：数字 $1$ 表示 Tvrtko 喜欢那个区间，而 $0$ 表示他不喜欢。你的程序最多可以发送 $500000$ 个这样的查询。 一旦你的程序计算出了舞者服装上的数字，它应在单独的一行上向标准输出打印符号 `!` 后跟从左到右出现的请求的数字序列。之后，你的程序应再次刷新输出并终止执行。 ## Background 题目来源：<https://hsin.hr/hio2024/>。翻译来自 [文心一言](https://yiyan.baidu.com/)。如果有更好的翻译请在讨论区提供。 [samples] ## Note **【解释说明】** 尽管在任务中舞者的数量总是为 $1000$，但为了说明目的，我们提供了一个当舞者数量为 $4$ 时的交互示例。 假设：舞者服装上的数字按顺序为 $2,1,4,3$。下面是一种可能的查询方案： - 查询 `? 1 2`，Tvrtko 数到了一对。 - 查询 `? 1 3`，Tvrtko 数到了一对。 - 查询 `? 1 4`，Tvrtko 数到了两对。 - 查询 `? 2 3`，Tvrtko 没有数到任何一对。 - 查询 `? 2 4`，Tvrtko 数到了一对。 - 查询 `? 3 4`，Tvrtko 数到了一对。 - 使用 `! 2 1 4 3` 输出答案。 **【评分细则】** 设 $Q$ 为你的程序在所有测试用例中发送的最大查询数。 如果 $Q > 5\times 10^5$，你的程序将得 $0$ 分。 否则，你的程序将获得的分数基于以下表格： | 范围 | 分数 | | :-----------: | :-----------: | | $4\times 10^4 \leq Q\leq 5\times 10^5$ | $30+70\times\dfrac{1/Q-1/500000}{1/40000-1/500000}$ | | $Q\leq 4\times 10^4$ | $100$ |