# [Solution] Omkar and the Meaning of Life solution codeforces | Codeforces Round #749

## Omkar and the Meaning of Life solution codeforces

It turns out that the meaning of life is a permutation π1,π2,β¦,ππp1,p2,β¦,pn of the integers 1,2,β¦,π1,2,β¦,n (2β€πβ€1002β€nβ€100). Omkar, having created all life, knows this permutation, and will allow you to figure it out using some queries.

A query consists of an array π1,π2,β¦,ππa1,a2,β¦,an of integers between 11 and πn. πa is not required to be a permutation. Omkar will first compute the pairwise sum of πa and πp, meaning that he will compute an array π s where π π=ππ+ππsj=pj+aj for all π=1,2,β¦,πj=1,2,β¦,n. Then, he will find the smallest index πk such that π πsk occurs more than once in π s, and answer with πk. If there is no such index πk, then he will answer with 00.

## Omkar and the Meaning of Life solution codeforces

You can perform at most 2π2n queries. Figure out the meaning of life πp.

Interaction

Start the interaction by reading single integer πn (2β€πβ€1002β€nβ€100) Β β the length of the permutation πp.

You can then make queries. A query consists of a single line “?π1π2β¦ππ?a1a2β¦an” (1β€ππβ€π1β€ajβ€n).

The answer to each query will be a single integer πk as described above (0β€πβ€π0β€kβ€n).

After making 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.

You can make at most 2π2n queries. Outputting the answer does not count as a query.

## Omkar and the Meaning of Life solution codeforces

Hack Format

To hack, first output a line containing πn (2β€πβ€1002β€nβ€100), then output another line containing the hidden permutation π1,π2,β¦,ππp1,p2,β¦,pn of numbers from 11 to πn.

Example
input

Copy
5

2

0

1

output

Copy
? 4 4 2 3 2

? 3 5 1 5 5

? 5 2 4 3 1

! 3 2 1 5 4


## Omkar and the Meaning of Life solution codeforces

Note

In the sample, the hidden permutation πp is [3,2,1,5,4][3,2,1,5,4]. Three queries were made.

The first query is π=[4,4,2,3,2]a=[4,4,2,3,2]. This yields π =[3+4,2+4,1+2,5+3,4+2]=[7,6,3,8,6]s=[3+4,2+4,1+2,5+3,4+2]=[7,6,3,8,6]. 66 is the only number that appears more than once, and it appears first at index 22, making the answer to the query 22.

The second query is π=[3,5,1,5,5]a=[3,5,1,5,5]. This yields π =[3+3,2+5,1+1,5+5,4+5]=[6,7,2,10,9]s=[3+3,2+5,1+1,5+5,4+5]=[6,7,2,10,9]. There are no numbers that appear more than once here, so the answer to the query is 00.

## Omkar and the Meaning of Life solution codeforces

The third query is π=[5,2,4,3,1]a=[5,2,4,3,1]. This yields π =[3+5,2+2,1+4,5+3,4+1]=[8,4,5,8,5]s=[3+5,2+2,1+4,5+3,4+1]=[8,4,5,8,5]. 55 and 88 both occur more than once here. 55 first appears at index 33, while 88 first appears at index 11, and 1<31<3, making the answer to the query 11.

Note that the sample is only meant to provide an example of how the interaction works; it is not guaranteed that the above queries represent a correct strategy with which to determine the answer.