P16408 [Algo Beat Contest 004 D] Displaced Permutation

Yet Another Interactive Problem About Permutation.

This is an interactive problem. The judge system has a hidden permutation $p$ of $1 \sim n$. Each time, you may query two integers $l, r$ such that $1 \le l \le r \le n$. The judge system will do the following: 1. Cyclically shift the subsegment $p[l, \ldots, r]$ by one. 2. The judge system will return a $\texttt{01}$ sequence $s$ of length $n$, where $s_i = 1$ if and only if **currently** $p_i = i$. In this problem, cyclically shifting a non-empty sequence by one means: insert the first element of the sequence at the end, and delete the first element. Your goal is to make the final permutation $p$ sorted in ascending order through a series of operations, i.e., for all $i \in [1, n]$, we have $p_i = i$. ### Interaction Your program needs to interact with the judge system via standard input and output. First, your program should read an integer $n$, which is the length of the hidden permutation. Then, your program should start making queries. Each query has the format: ``` ? l r ``` where $l, r$ are positive integers satisfying $1 \le l \le r \le n$. After each query, the judge system will return a $\texttt{01}$ string of length $n$, and your program should read it from standard input. When you think that $p$ is already sorted in ascending order, you should report it in the format: ``` ! ``` After outputting the answer, your program should terminate immediately. You can make **at most $2026$ queries**. If the number of queries exceeds the limit, or the answer is wrong, or the format does not meet the requirements, the judge system will return Wrong Answer. Note: After each output, you must flush the buffer. For example, in C++ use `cout

N/A

N/A

#### Sample Explanation #1 In the sample, the hidden permutation is $p = [4, 1, 3, 2]$. Explanation: - Query $l = 1, r = 4$. Then $p$ becomes $[1, 3, 2, 4]$, and the judge returns $\texttt{1001}$. - Query $l = 2, r = 3$. Then $p$ becomes $[1, 2, 3, 4]$, and the judge returns $\texttt{1111}$. - Now you think that $p$ has been sorted in ascending order, so you report it. #### Constraints - $1 \le n \le 1000$. - The hidden $p$ in the judge system is a permutation of $1 \sim n$. Translated by ChatGPT 5