CF2157G Isaac's Queries

[wavetearz - contemporary chemical bonds](https://soundcloud.com/wavetearz/contemporary-chemical-bonds) ⠀ You have reached the final level of the popular roguelike game "Isaac's Keybindings". Instead of a boss, you encounter a shopkeeper who holds an hidden array of integers $ a_1, a_2, \ldots, a_n $ , where $ 0 \leq a_i < 2^{30} $ for each $ i $ in $ [1, n] $ . It is guaranteed that the array is generated randomly, i.e., each $ a_i $ ( $ 1 \leq i \leq n $ ) is an integer independently generated uniformly at random in $ [0, 2^{30}) $ , in all the tests excluding the example. Let $ f(u, v) = a_u \oplus a_{u+1} \oplus \ldots \oplus a_v $ , where $ \oplus $ is the bitwise $ \texttt{XOR} $ . You can ask queries of the following form: $ \texttt{? u v} $ , with $ 1 \leq u \leq v \leq n $ . The answer to the query is: - $ -1 $ , if $ f(u, v) = 0 $ ; - $ \lfloor \log_2(f(u, v)) \rfloor $ otherwise. Each query has a cost of $ \frac{1}{v-u+1} $ robocoins. On each test, you are given $ 300 $ robocoins in total to pass at most $ 30 $ test cases (that is, you can spend $ 10 $ robocoins on average for a single test case). If your balance ever becomes negative you lose. Note that your robocoin balance does not need to be an integer at any moment. Find the answer to all possible $ \frac{n(n+1)}{2} $ queries without losing.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 30 $ ). The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ n = 3 $ or $ n = 100 $ ) — the length of the array $ a_1, a_2, \ldots, a_n $ . It is guaranteed that the array is generated randomly in all the tests excluding the example. There are exactly $ 50 $ tests in this problem (including the example). The example has $ t = 1 $ and $ n = 3 $ , and all the other tests have $ t = 30 $ and $ n = 100 $ . Hacks are not allowed in this problem.

N/A

In the example, the hidden array is $ [a_1, a_2, a_3] = [2, 4, 6] $ . - First, you ask $ \texttt{? 1 2} $ . Since $ f(1, 2) = a_1 \oplus a_2 = 6 $ , the answer is $ \lfloor \log_2(6) \rfloor = 2 $ . - Then, you ask $ \texttt{? 1 3} $ . Since $ f(1, 3) = a_1 \oplus a_2 \oplus a_3 = 0 $ , the answer is $ -1 $ . - Then, you ask $ \texttt{? 2 3} $ . Since $ f(2, 3) = a_2 \oplus a_3 = 2 $ , the answer is $ \lfloor \log_2(2) \rfloor = 1 $ . Now, even without knowing the hidden array, you claim the answer to all the possible $ 6 $ queries. For example, you claim that the answer to $ \texttt{? 1 1} $ is $ 1 $ . You have spent $ 1/2 + 1/3 + 1/2 = 4/3 $ robocoins, which is less than the allowed $ 300 $ robocoins.