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

To output your answer, print a single line “!𝑝1𝑝2…𝑝𝑛!p1p2…pn” then terminate.

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.


Omkar and the Meaning of Life solution codeforcesYet another MEX problem solution codechefYet another MEX problem solution codechefYet another MEX problem solution codechef

Leave a Comment

Your email address will not be published. Required fields are marked *