Secret Permutation

Time limit1.5sMemory limit1024 MB

Summary

Recover a hidden permutation P of 1 to N using queries that return the sum of absolute differences of P along a chosen index order V.

Level: Medium7 of 10
Topics: Math, Implementation
Solved: No attempts yet

Problem

The Scientific Committee has hidden a permutation $P$ of all integers from 1 to $N$ (3 ≤ $N$ ≤ 256). You need to find it. $P$ is fixed, and the grader is not adaptive.

You may ask queries with another permutation $V$ of the integers from 1 to $N$ as the parameter. The query $\text{query}(V)$ returns

$\text{query}(V) = \sum_{i=1}^{N-1} |P[V_i] - P[V_{i+1}]|$

After a number of queries, find $P$ , or any other permutation $P'$ that cannot be distinguished from $P$ . Two permutations are indistinguishable if every possible query returns the same answer for both.

Examples1

Example 1
Input
```
3
```
Expected output
```
? 1 2 3
! 1 2 3
```