CF2209C Find the Zero

This is an interactive problem. You are given an integer $ n $ . There is a hidden array $ a $ of length $ 2n $ . Each integer from $ 1 $ to $ n $ appears exactly once in $ a $ . The rest of the elements are all $ 0 $ . You can make the following type of query: - Choose two integers $ i $ and $ j $ ( $ 1 \le i,j \le 2n $ , $ i \ne j $ ). The judge will respond with $ 1 $ if $ a_i=a_j $ , and will respond with $ 0 $ otherwise. Find any integer $ k $ ( $ 1 \le k \le 2n $ ) such that $ a_k=0 $ in no more than $ n+1 $ queries. Note that the interactor is adaptive, which means that the hidden array $ a $ may change depending on your queries but will not contradict previous queries.

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 an integer $ n $ ( $ 2 \le n \le 10^4 $ ). The length of the hidden array $ a $ will be $ 2n $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^4 $ .

N/A

In the first example test case, the hidden array $ a $ is $ [0,1,0,2] $ : - In the first query, $ (i,j)=(1,2) $ . Since $ a_1=0 $ , $ a_2=1 $ , $ a_1 \ne a_2 $ , the judge responds with $ 0 $ . - In the second query, $ (i,j)=(3,1) $ . Since $ a_3=0 $ , $ a_1=0 $ , $ a_3 = a_1 $ , the judge responds with $ 1 $ . - The program reports $ k=3 $ as an answer. Since $ a_3=0 $ , the answer is correct. In the second example test case, the hidden array $ a $ is $ [3,2,0,1,0,0] $ : - In the first query, $ (i,j)=(5,6) $ . Since $ a_5=0 $ , $ a_6=0 $ , $ a_5 = a_6 $ , the judge responds with $ 1 $ . - In the second query, $ (i,j)=(2,4) $ . Since $ a_2=2 $ , $ a_4=1 $ , $ a_2 \ne a_4 $ , the judge responds with $ 0 $ . - In the third query, $ (i,j)=(1,3) $ . Since $ a_1=3 $ , $ a_3=0 $ , $ a_1 \ne a_3 $ , the judge responds with $ 0 $ . - The program reports $ k=6 $ as an answer. Since $ a_6=0 $ , the answer is correct.