Hidden Permutations solution codeforces

Hidden Permutations solution codeforces

 

This is an interactive problem.

The jury has a permutation pp of length nn and wants you to guess it. For this, the jury created another permutation qq of length nn. Initially, qq is an identity permutation (qi=iqi=i for all ii).

You can ask queries to get qiqi for any ii you want. After each query, the jury will change qq in the following way:

  • At first, the jury will create a new permutation qq′ of length nn such that qi=qpiqi′=qpi for all ii.
  • Then the jury will replace permutation qq with pemutation qq′.

You can make no more than 2n2n queries in order to quess pp.

Input Hidden Permutations solution codeforces

The first line of input contains a single integer tt (1t10001≤t≤1000) — the number of test cases.

Interaction

Interaction in each test case starts after reading the single integer nn (1n1041≤n≤104) — the length of permutations pp and qq.

To get the value of qiqi, output the query in the format ?? ii (1in1≤i≤n). After that you will receive the value of qiqi.

You can make at most 2n2n queries. After the incorrect query you will receive 00 and you should exit immediately to get Wrong answer verdict.

When you will be ready to determine pp, output pp in format !! p1p1 p2p2  pnpn. 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 2n2n 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 of nn over all test cases doesn’t exceed 104104. 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 tt — the number of test cases.

The first line of each test case contains the single integer nn — the length of the permutations pp and qq. The second line of each test case contains nn integers p1,p2,,pnp1,p2,…,pn — the permutation for this test case.

Example Hidden Permutations solution codeforces
input

Copy
2
4

3

2

1

4

2

4

4
Hidden Permutations solution codeforces output

Copy
? 3

? 2

? 4

! 4 2 1 3

? 2

? 3

? 2

! 1 3 4 2
Note

In the first test case the jury guessed the permutation p=[4,2,1,3]p=[4,2,1,3].

Before the first query q=[1,2,3,4]q=[1,2,3,4] so answer for the query will be q3=3q3=3.

Before the second query q=[4,2,1,3]q=[4,2,1,3] so answer for the query will be q2=2q2=2.

Before the third query q=[3,2,4,1]q=[3,2,4,1] so answer for the query will be q4=1q4=1.

In the second test case the jury guessed the permutation p=[1,3,4,2]p=[1,3,4,2].

Empty strings are given only for better readability. There will be no empty lines in the testing system.

Leave a Comment

Your email address will not be published.