P11478 [COCI 2024/2025 #3] 处理器 / Procesor

译自 [COCI 2024/2025 #3](https://hsin.hr/coci/) T5。$\texttt{1s,0.5G}$。满分为 $120$。 为了方便测试，公开[交互库](https://www.luogu.com.cn/paste/1gl6aook)。

**这是一道交互题**。 有一个初始时为空的数组 $a$。 $n$ 次操作，第 $i$ 次操作向 $a$ 的末尾添加 $x_i$ 个整数。 每次操作后，通过若干次询问，你需要找到最小的**未被标记**的整数对应的下标 $x$，并给 $a_x$ 打标记。 每次询问，你可以询问两个**未被标记**的整数 $a_i,a_j$ 的大小关系。 设当前数组长度为 $l$，保证 $\forall 1\le i\lt j\le l$，$a_i\lt a_j$ 和 $a_j\lt a_i$ **恰有一个成立**。换句话说，**保证数组内元素两两不同**。 ### 实现细节 首先读入一个正整数 $n$。接下来依次处理 $n$ 次操作。 对于第 $i$ 次操作，读入一个正整数 $x_i$，表示增加的整数数量。 接下来你可以按照以下格式询问若干次： - $\texttt{?}$ $i$ $j$：询问 $a_i,a_j$ 的大小关系。 - 返回 $0$，表示 $a_i\lt a_j$；返回 $1$，表示 $a_i\gt a_j$。 - 令当前数组长度为 $l$，你需要保证 $1\le i,j\le l$。 - 你需要保证 $i\neq j$，且 $a_i,a_j$ 未被标记。 按以下格式回答： - $\texttt{!}$ $x$：当前数组内未被标记的最小整数为 $a_x$。 **回答后立刻读入下一个整数 $x_{i+1}$，若这是最后一次操作则立刻结束程序。** **在每次询问或者回答后，都要换行并刷新缓冲区。** 刷新缓冲区的方式：C++ 中的 `std::cout.flush()`，`std::cout

无

无

### 样例解释 样例 $1$ 中，$a=[3,2,4,1,5]$。 - 查询 $a_1$ 与 $a_2$：$a_1\gt a_2$，返回 $1$； - 查询 $a_1$ 与 $a_3$：$a_1\lt a_3$，返回 $0$； - 查询 $a_2$ 与 $a_3$：$a_2\lt a_3$，返回 $0$。 不难发现 $a_2$ 为当前未标记的最小值，所以回答 $2$。接下来继续处理剩余的两次操作。 ### 数据范围 对于 $100\%$ 的数据，保证： - $1\le n\le 40$； - $1\le x_i,\sum x_i\le 2\, 000$。 - 数组内整数两两不同。 ### 计分方式 令你的程序询问次数的最大值为 $q$。 - $q\le 2\, 700$，得 $120$ 分。 - $2\, 700 \lt q\le 7\, 000$，得 $75$ 分。 - $7\, 000 \lt q\le 2\times 10^4$，得 $35$ 分。 - $2\times 10^4 \lt q\le 8\times 10^4$，得 $15$ 分。 - $8\times 10^4\lt q$，得 $0$ 分。