CF2156D Find the Last Number

This is an interactive problem. There is a hidden permutation $ ^{\text{∗}} $ $ p $ of length $ n $ . You are allowed to interact with it by asking the following query at most $ 2n $ times: - Select two integers $ i $ and $ x $ such that $ 1\le i\le \boldsymbol{n - 1} $ and $ 1\le x\le 10^9 $ . The grader will respond $ \mathtt{0} $ if $ p_i \mathbin{\&} x $ $ ^{\text{†}} $ is equal to zero, and $ \mathtt{1} $ otherwise. Important: You cannot make queries involving the last element $ p_n $ (because $ i\le n - 1 $ ). Your goal is to determine the value of the last element of the permutation, $ p_n $ , using at most $ 2n $ queries. Note that the interactor is non-adaptive. This means that the hidden permutation $ p $ is fixed at the beginning and will not change based on your queries. $ ^{\text{∗}} $ A permutation of length $ n $ is an array consisting of $ n $ distinct integers from $ 1 $ to $ n $ in arbitrary order. For example, $ [2,3,1,5,4] $ is a permutation, but $ [1,2,2] $ is not a permutation ( $ 2 $ appears twice in the array), and $ [1,3,4] $ is also not a permutation ( $ n=3 $ but there is $ 4 $ in the array). $ ^{\text{†}} $ $ \& $ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^4 $ ) — the length of permutation $ p $ . For each test case, after reading $ n $ , you should begin the interaction and find the answer before proceeding to the next test case. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^4 $ .

N/A

In the first test, the interaction proceeds as follows. SolutionJuryExplanation $ \texttt{2} $ There are 2 test cases. $ \texttt{2} $ In the first test case, the hidden permutation is $ [2,1] $ (of length $ 2 $ ). $ \texttt{? 1 1} $ $ \texttt{0} $ The solution queries $ p_1 \mathbin{\&}1 $ . Since $ p_1 = 2 $ and $ 2 \mathbin{\&} 1 = 0 $ , the jury responds with $ 0 $ . $ \texttt{? 1 2} $ $ \texttt{1} $ The solution queries $ p_1 \mathbin{\&}2 $ . Since $ p_1 = 2 $ and $ 2 \mathbin{\&} 2 = 2 $ , the jury responds with $ 1 $ . $ \texttt{! 1} $ The solution determines that the last element is $ 1 $ since it knows that the first element is not $ 1 $ from the first query. $ \texttt{3} $ In the second test case, the hidden permutation is $ [1,3,2] $ (of length $ 3 $ ). $ \texttt{? 1 3} $ $ \texttt{1} $ The solution queries $ p_1 \mathbin{\&}3 $ . Since $ p_1 = 1 $ and $ 1 \mathbin{\&} 3 = 1 $ , the jury responds with $ 1 $ . $ \texttt{? 1 2} $ $ \texttt{0} $ The solution queries $ p_1 \mathbin{\&}2 $ . Since $ p_1 = 1 $ and $ 1 \mathbin{\&} 2 = 0 $ , the jury responds with $ 0 $ . $ \texttt{? 2 3} $ $ \texttt{1} $ The solution queries $ p_2 \mathbin{\&}3 $ . Since $ p_2 = 3 $ and $ 3 \mathbin{\&} 3 = 3 $ , the jury responds with $ 1 $ . $ \texttt{! 2} $ The solution determines that the last element is $ 2 $ .Note that the empty lines in the example input and output are only for readability. They do not appear in the actual interaction.