P16408 [Algo Beat Contest 004 D] Displaced Permutation

Yet Another Interactive Problem About Permutation

这是一道交互题。 评测系统有一个隐藏的 $1 \sim n$ 的排列 $p$。 每次你可以询问两个整数 $l, r$ 使得 $1 \le l \le r \le n$。评测系统会执行以下步骤： 1. 将 $p$ 的子段 $p[l, \ldots, r]$ 循环移位一次。 2. 评测系统会返回一个长度为 $n$ 的 $\texttt{01}$ 序列 $s$，其中 $s_i = 1$ 当且仅当 **当前** $p_i = i$。 在本题中，对一个非空序列循环移位一次定义为：将序列首个元素的值插入到序列末尾，并删除序列首个元素。 你的目标是通过一系列操作，使得最终的排列 $p$ 升序排列，即对于所有 $i \in [1, n]$，有 $p_i = i$。 ### 交互方式 你的程序需要通过标准输入输出与评测系统交互。 首先，程序应读入一个数 $n$，表示隐藏的排列的长度。接下来，程序应开始询问，每次询问格式为： ``` ? l r ``` 其中 $l, r$ 是两个正整数，满足 $1 \le l \le r \le n$。每次询问后，评测系统会返回一个长度为 $n$ 的 $\texttt{01}$ 串，你的程序应从标准输入读取该返回值。 当你认为 $p$ 已经升序排列时，应报告，格式为： ``` ! ``` 输出答案后，你的程序应立即结束。 你最多可以进行 **不超过 $2026$ 次询问**。如果询问次数超过限制，或者答案错误，或者格式不符合要求，评测系统将判定为错误答案。 注意：每次输出后必须刷新缓冲区，例如 C++ 中使用 `cout

无

无

#### 样例解释 #1 样例中隐藏的排列 $p = [4, 1, 3, 2]$。解释： - 询问 $l = 1, r = 4$，$p$ 变为 $[1, 3, 2, 4]$，返回 $\texttt{1001}$。 - 询问 $l = 2, r = 3$，$p$ 变为 $[1, 2, 3, 4]$，返回 $\texttt{1111}$。 - 此时你认为 $p$ 已经升序排序，因此报告。 #### 数据范围 - $1 \le n \le 1000$。 - 评测系统中隐藏的 $p$ 是一个 $1 \sim n$ 的排列。