Background

Submission notes:

1. Do not include any header files.
2. Add the following at the beginning of the file:

   #include <vector>
   #include <array>
   std::vector<int> sorting(int);
   std::vector<int> ask_question(std::vector<std::array<int, 2>>);
   

3. Submit using $\texttt{C++\,\red{20/23}}$.

Problem Description

This is an interactive problem. In this problem, the interaction library is adaptive.

Alice and Bob are playing a game. Alice has $N$ items, numbered $0\sim N-1$. The value of item $i$ is a non-negative integer $A[i]$.

Alice knows the values of all items, but Bob only knows the number of items $N$, and that all item values are non-negative integers. Bob’s goal is to sort the items in non-decreasing order of value. In other words, Bob needs to find a permutation $P$ of $0\sim N-1$ such that:

• For any $0\le i\le N-2$, $A[P[i]]\le A[P[i+1]]$.

To do this, Bob can ask Alice $10\,000$ queries.

Query

1. Bob provides a tree with $N$ nodes, where the nodes are numbered $0\sim N-1$. The node weight of node $i$ is $A[i]$.
2. Alice selects any maximum independent set of this tree (it may be empty) and returns it to Bob. Then Alice clears this tree.

   • In other words, Alice chooses a set of nodes $V\subseteq \{0,1,\ldots,N-1\}$ (which may be empty), such that no two nodes in $V$ are connected by an edge, and $\sum_{v\in V} A[v]$ is maximized.

     If there are multiple valid sets, Alice will choose one arbitrarily.

Help Bob achieve the goal using as few queries as possible.

Implementation Details

This is a functional interactive problem. You do not need to, and should not, implement the main function.

You should implement the following function:

vector<int> sorting(int N)

• $N$: the number of items.
• Return an array $P$ that sorts the item indices in non-decreasing order of value. If there are multiple solutions, you may return any of them.
• This function is called exactly once.

You may call the following function:

vector<int> ask_question(vector<array<int, 2>> threads)

• Represents one query from Bob to Alice.
• threads: an array of pairs of size $N-1$, describing the edges of the tree. Each element $[a,b]$ in threads represents an edge $(a,b)$.
• threads must describe a tree.
• Returns an integer array $C$ of size $N$. If the chosen maximum independent set contains $i$, then $C[i]=1$; otherwise $C[i]=0$.
  • If there are multiple solutions, Alice will return one arbitrarily. Note that if you pass the same threads array multiple times within the same test case, the return value may differ.
• In each test case, this function can be called at most $10\,000$ times.

Input Format

The input format of the sample grader is as follows:

• Line $1$: $N$
• Line $2$: $A[0] A[1] \dots A[N - 1]$

The provided sample grader is only guaranteed to work properly when $A[i]$ is an integer between $0$ and $10^9$ (inclusive).

Output Format

The sample grader prints the array returned by your code in the sorting function and the number of calls to ask_question in the following format:

• Line $1$: Suppose sorting returns an array $P$ of length $M$, print $P[0] P[1] \dots P[M - 1]$.
• Line $2$: The number of calls to ask_question, $Q$.

Note that the sample grader may be different from the grader used in the actual evaluation.

6
5 3 3 0 8 1

3 5 1 2 0 4
2

Hint

Constraints

• $5\le N\le 1\, 000$.
• $A[i]$ is a non-negative integer. Note that there is no upper bound on $A[i]$.
• In each test case, you can call ask_question at most $10\,000$ times.
• The interaction library is adaptive. In other words, $A$ is not fixed and may change depending on how ask_question is called. When answering, the interaction library guarantees that there exists an array $A$ consistent with all previous answers from ask_question.
• In each test case, the interaction library uses at most $2$ seconds and $16\, \mathrm{MiB}$ of memory.

Subtasks

Scoring

Subtasks $1,2$

If your answer is valid, you get full score.

Subtasks $3,4,5$

If the answer is wrong, or the program terminates abnormally, you get $0$ points.

Otherwise, let $Q_{\max}$ be the maximum number of calls to ask_question within a single test case of this subtask, and compute $X$:

This subtask receives $X\%$ of its score.

Example

Consider $N = 6$ and the array $A$ representing the values of Alice’s items is $[5, 3, 3, 0, 8, 1]$.

The grader first calls:

sorting(6)

Your code may interact as follows:

ask_question([[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]])
ask_question([[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]])

In the first call, if Alice selects items $0, 2, 4$, the total value is $5 + 3 + 8 = 16$, which is the maximum. Therefore, this call returns $[1, 0, 1, 0, 1, 0]$.

In the second call, the item sets Alice can choose (while satisfying the condition) are $\{1, 2, 4, 5\}$ and $\{1, 2, 3, 4, 5\}$. Therefore, this call returns $[0, 1, 1, 0, 1, 1]$ or $[0, 1, 1, 1, 1, 1]$.

Consider the following interactions:

ask_question([[0, 1], [2, 3], [4, 5]])
ask_question([[0, 1], [1, 2], [2, 3], [3, 0], [4, 5]])

In the first call, this is not a valid call because the size of the threads array is not $N - 1$.

In the second call, this is not a valid call because the given graph is not a tree.

There are two valid integer arrays $P$:

• $[3, 5, 1, 2, 0, 4]$
• $[3, 5, 2, 1, 0, 4]$

Therefore, the function must return one of these two arrays.

Translated by ChatGPT 5