Hidden Permutations solution codeforces
This is an interactive problem.
The jury has a permutationof length and wants you to guess it. For this, the jury created another permutation of length . Initially, is an identity permutation ( for all ).
You can ask queries to getfor any you want. After each query, the jury will change in the following way:
- At first, the jury will create a new permutation of length such that for all .
- Then the jury will replace permutation with pemutation .
You can make no more thanqueries in order to quess .
The first line of input contains a single integer( ) — the number of test cases.
Interaction in each test case starts after reading the single integer( ) — the length of permutations and .
To get the value of, output the query in the format ( ). After that you will receive the value of .
You can make at most Wrong answer verdict.queries. After the incorrect query you will receive and you should exit immediately to get
When you will be ready to determine, output in format . After this you should go to the next test case or exit if it was the last test case. Printing the permutation is not counted as one of queries.
After printing a query do not forget to output 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 documentation for other languages.
It is guaranteed that the sum ofover all test cases doesn’t exceed . The interactor is not adaptive in this problem.
Hidden Permutations solution codeforces Hacks:
To hack, use the following format:
The first line contains the single integer— the number of test cases.
The first line of each test case contains the single integer— the length of the permutations and . The second line of each test case contains integers — the permutation for this test case.
2 4 3 2 1 4 2 4 4
? 3 ? 2 ? 4 ! 4 2 1 3 ? 2 ? 3 ? 2 ! 1 3 4 2
In the first test case the jury guessed the permutation.
Before the first queryso answer for the query will be .
Before the second queryso answer for the query will be .
Before the third queryso answer for the query will be .
In the second test case the jury guessed the permutation.
Empty strings are given only for better readability. There will be no empty lines in the testing system.