CF2150E2 Hidden Single (Version 2)

[AdhesiveWombat - Overdrive](https://soundcloud.com/adhesivewombat/adhesivewombat-overdrive) ⠀ The two versions have different constraints on $ t $ , $ n $ , and the maximum number of queries, and solving one of the two versions does not necessarily solve the other. You may want to read both versions. Hacks are disabled in both versions. This is an interactive problem. There is a hidden array $ a_1, a_2, \ldots, a_{2n-1} $ containing all the numbers from $ 1 $ to $ n $ , and all of them appear twice except one (which only appears once). You can ask queries in the following format, where $ S $ is a subset of $ \{1, 2, \ldots, 2n-1\} $ and $ x $ is an integer in $ [1, n] $ : - $ \texttt{ask(S, x)} $ : does there exist $ i \in S $ such that $ a_i = x $ ? Find the number appearing exactly once, using at most $ 925 $ queries. You don't need to find its position. Note that the interactor is not adaptive, which means that the hidden array does not depend on the queries you make.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 20 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ n = 300 $ ) — the maximum value in the hidden array $ a_1, a_2, \ldots, a_{2n-1} $ . There are exactly $ 50 $ tests in this problem (including the example). The example has $ t = 1 $ , and all the other tests have $ t = 20 $ .

N/A

In the first test case, $ n = 300 $ , so the hidden array has length $ 2n-1 = 599 $ . \#Contestant printsInteractor repliesExplanation1? 187 1 10Query: does $ a_1=187 $ ? No.2! 187We feel lucky, and claim that the answer is $ 187 $ . Fortunately, the answer is correct.We have asked $ 1 $ query (printing the answer does not count as a query), which is less than the maximum allowed number of queries ( $ 925 $ ).