# [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.    