Secret Permutation

Task

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

Interaction protocol

Your solution to this problem must be written inside this function:

void solve(int N);

You are free to write and call additional functions but you're not allowed to write a main() function.

In your endeavor, you are allowed to ask queries that take as parameter another permutation $V$ of all the integers from $1$ to $N$:

int query(std::vector<int> V);

This function will return $\sum_{i = 1}^{N-1} abs(P[V[i]] - P[V[i + 1]])$. Whenever you want to perform a query, call this function with a permutation $V$ of all the integers from $1$ to $N$ as parameter. You will be graded based on the number of times you call this function. Performing a number of queries, you are to discover permutation $P$, or any other permutation $P$' that is indistinguishable from $P$.

When you're confident you've discovered permutation $P$, call this function with $P$ as a parameter.

void answer(std::vector<int> P);

Calling this function will terminate the program.

Note that both permutations $P$ and $V$ are represented as a $0$-indexed std::vector<int> when supplied as parameters.

Sample implementation

Sample code to illustrate the Interaction section:

#include "permutation.h"

void solve(int N) {
  if (N == 2) {
    std::vector<int> V = {1, 2};
    int qAns = query(V);
    if (qAns == 1) {
      std::vector<int> P = {1, 2};
      answer(P);
    }
  }
}

Sample grader

For local testing you can download two files from "Attachments": grader.cpp and permutation.h.

The Grader reads from Standard Input an integer $N$ - the size of the hidden permutation and $N$ distinct integers - the hidden permutation. Then, the Grader calls the solve() function you must implement.

At Standard Output the Grader will output:

• for every query() call: the queried permutation and the answer to the query;
• for the answer() call: the verdict (Correct or Wrong Answer), $N$ and $Q$ - the size of the permutation and the number of queries you used.

Constraints and clarifications

• $3 \leq N \leq 256$
• Two permutations are indistinguishable if queried in all possible ways they both yield the same answers.

Scoring

Each of the test cases is scored as follows:

If you fail to discover one of the correct permutations, then $0\%$ of the score is awarded.

Otherwise, let $Q$ be the number of queries you needed to solve the test case.

• If $Q ≤ N$ then $100\%$ of the score is awarded.
• If $N ≤ Q ≤ 2 \cdot N$ queries then $\displaystyle \left(100 - \frac{40 \cdot (Q - N)}{N} \right)\%$ (between $60\%$ and $100\%$ , increasing as $Q$ decreases) of the score is awarded.
• If $2 \cdot N ≤ Q ≤ N^2$ queries then $\displaystyle \left(60- \frac{40 \cdot (Q - 2 \cdot N)}{N^2 - 2 \cdot N}\right)\%$ (between $20\%$ and $60\%$ , increasing as $Q$ decreases) of the score is awarded.
• If $N^2 ≤ Q$ then $20\%$ of the score is awarded.

The total score of this task will be rounded to $2$ decimal places.