CF1762D GCD Queries

This is an interactive problem. There is a secret permutation $ p $ of $ [0,1,2,\ldots,n-1] $ . Your task is to find $ 2 $ indices $ x $ and $ y $ ( $ 1 \leq x, y \leq n $ , possibly $ x=y $ ) such that $ p_x=0 $ or $ p_y=0 $ . In order to find it, you are allowed to ask at most $ 2n $ queries. In one query, you give two integers $ i $ and $ j $ ( $ 1 \leq i, j \leq n $ , $ i \neq j $ ) and receive the value of $ \gcd(p_i,p_j)^\dagger $ . Note that the permutation $ p $ is fixed before any queries are made and does not depend on the queries. $ ^\dagger $ $ \gcd(x, y) $ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $ x $ and $ y $ . Note that $ \gcd(x,0)=\gcd(0,x)=x $ for all positive integers $ x $ .

N/A

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 $ [1,0] $ , with length $ 2 $ . $ \texttt{? 1 2} $ $ \texttt{1} $ The solution requests $ \gcd(p_1,p_2) $ , and the jury responds with $ 1 $ . $ \texttt{! 1 2} $ $ \texttt{1} $ The solution knows that either $ p_1=0 $ or $ p_2=0 $ , and prints the answer. Since the output is correct, the jury responds with $ 1 $ and continues to the next test case. $ \texttt{5} $ In the second test case, the hidden permutation is $ [2,4,0,1,3] $ , with length $ 5 $ . $ \texttt{? 1 2} $ $ \texttt{2} $ The solution requests $ \gcd(p_1,p_2) $ , and the jury responds with $ 2 $ . $ \texttt{? 2 3} $ $ \texttt{4} $ The solution requests $ \gcd(p_2,p_3) $ , and the jury responds with $ 4 $ . $ \texttt{! 3 3} $ $ \texttt{1} $ The solution has somehow determined that $ p_3=0 $ , and prints the answer. Since the output is correct, the jury responds with $ 1 $ .Note that the empty lines in the example input and output are for the sake of clarity, and do not occur in the real interaction. After each test case, make sure to read $ 1 $ or $ -1 $ .