CF1815B Sum Graph

This is an interactive problem. There is a hidden permutation $ p_1, p_2, \dots, p_n $ . Consider an undirected graph with $ n $ nodes only with no edges. You can make two types of queries: 1. Specify an integer $ x $ satisfying $ 2 \le x \le 2n $ . For all integers $ i $ ( $ 1 \le i \le n $ ) such that $ 1 \le x-i \le n $ , an edge between node $ i $ and node $ x-i $ will be added. 2. Query the number of edges in the shortest path between node $ p_i $ and node $ p_j $ . As the answer to this question you will get the number of edges in the shortest path if such a path exists, or $ -1 $ if there is no such path. Note that you can make both types of queries in any order. Within $ 2n $ queries (including type $ 1 $ and type $ 2 $ ), guess two possible permutations, at least one of which is $ p_1, p_2, \dots, p_n $ . You get accepted if at least one of the permutations is correct. You are allowed to guess the same permutation twice. 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).

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 10^3 $ ) — the length of the permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^3 $ .

The interaction for each test case begins by reading the integer $ n $ . Then, make at most $ 2n $ queries: - If you want to make a type $ 1 $ query, output "+ x". $ x $ must be an integer between $ 2 $ and $ 2n $ inclusive. After doing that read $ 1 $ or $ -2 $ . If you read $ 1 $ your query was valid, otherwise it was invalid or you exceed the limit of queries, and your program must terminate immediately to receive a Wrong Answer verdict. - If you want to make a type $ 2 $ query, output "? i j". $ i $ and $ j $ must be integers between $ 1 $ and $ n $ inclusive. After that, read in a single integer $ r $ ( $ -1 \le r \le n $ ) — the answer to your query. If you receive the integer $ −2 $ instead of an answer, it means your program has made an invalid query, or has exceeded the limit of queries. Your program must terminate immediately to receive a Wrong Answer verdict. At any point of the interaction, if you want to guess two permutations, output "! $ p_{1,1} $ $ p_{1,2} $ $ \dots $ $ p_{1,n} $ $ p_{2,1} $ $ p_{2,2} $ $ \dots $ $ p_{2,n} $ ". Note that you should output the two permutations on the same line, and no exclamation mark is needed to separate the two permutations. After doing that read $ 1 $ or $ -2 $ . If you read $ 1 $ your answer was correct, otherwise it was incorrect and your program must terminate immediately to receive a Wrong Answer verdict. After that, move on to the next test case, or terminate the program if there are none. Note that reporting the answer does not count as a query. Note that even if you output a correct permutation, the second permutation should be a permutation and not an arbitrary array. At any point, if you continue interaction after reading in the integer $ -2 $ , you can get an arbitrary verdict because your solution will continue to read from a closed stream. After printing a query or the answer do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see the documentation for other languages. Interactor is non-adaptive. This means that all permutations are fixed before the interaction starts. Hacks To make a hack, use the following format. The first line should contain a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. The first line of each test case should contain a single integer $ n $ ( $ 2 \le n \le 10^3 $ ) — the length of the permutation. The second line of each test case should contain $ n $ distinct integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ) — the hidden permutation. The sum of $ n $ over all test cases should not exceed $ 10^3 $ .

In the first test case, $ n=6 $ and the hidden permutation $ p = [1,4,2,5,3,6] $ . Firstly, make a type $ 1 $ query on $ x=12, 2, 3 $ respectively. This adds four edges to the graph in total: - An edge that connects node $ 6 $ and node $ 6 $ . - An edge that connects node $ 1 $ and node $ 1 $ . - An edge that connects node $ 1 $ and node $ 2 $ . - An edge that connects node $ 2 $ and node $ 1 $ . Since all of these queries are valid, the interactor returns $ 1 $ after each of them. Then, query the number of edges in the shortest path between node $ p_1 = 1 $ and $ p_3 = 2 $ , which is equal to $ 1 $ . Then, make a type $ 1 $ query on $ x=5 $ . This adds four edges to the graph in total: - An edge that connects node $ 1 $ and node $ 4 $ . - An edge that connects node $ 2 $ and node $ 3 $ . - An edge that connects node $ 3 $ and node $ 2 $ . - An edge that connects node $ 4 $ and node $ 1 $ . Since this query is valid, the interactor returns $ 1 $ . Then, query the number of edges in the shortest path between node $ p_1 = 1 $ and $ p_5 = 3 $ , which is equal to $ 2 $ . Then, query the number of edges in the shortest path between node $ p_4 = 5 $ and $ p_5 = 3 $ . Such a path doesn't exist, therefore the interactor returns $ -1 $ . Afterwards, due to some magic, two possible permutations that can be $ p $ are determined: the first permutation is $ [1,4,2,5,3,6] $ and the second permutation is $ [1,2,3,4,5,6] $ . Since the first permutation is equal to the hidden permutation, this test case is solved correctly. In total, $ 7 $ queries are used, which is within the limit of $ 2 \cdot 6 = 12 $ queries. Since the answer is correct, the interactor returns $ 1 $ . In the second test case, $ n=2 $ and the hidden permutation is $ p = [2,1] $ . Since there are only $ 2! = 2 $ possible permutations, no queries are needed. It is sufficient to just output the two permutations, $ [1,2] $ and $ [2,1] $ . In total, $ 0 $ queries are used, which is within the limit of $ 2 \cdot 2 = 4 $ queries. Since the answer is correct, the interactor returns $ 1 $ .