P15587 [KTSC 2026] Sorting / Sorting

Submission notes: 1. Do **not** include any header files. 2. Add the following at the beginning of the file: ```cpp #include #include std::vector sorting(int); std::vector ask_question(std::vector); ``` 3. Submit using $\texttt{C++\,\red{20/23}}$.

**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: ```cpp vector 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: ```cpp vector ask_question(vector 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.

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

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.

### 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 | ID | Score | Constraints | | :-: | :-: | :- | | $1$ | $ 7$ | $N=5$ | | $2$ | $ 8$ | $N \le 100$ | | $3$ | $10$ | $\forall 0\le i\lt N$, there exists at most one $i$ such that $A[i]\gt 0$ | | $4$ | $30$ | $\forall 0\le i\lt \frac{N}{2}$, $A[i]=0$ | | $5$ | $45$ | No additional constraints | ### 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$: | Condition | $X=$ | | :- | :- | | $10\, 000 \lt Q_{\max}$ | $0$ | | $80 \lt Q_{\max}\le 10\, 000$ | $90 - 35\log_{10}\left(\frac{Q_{\max}}{80}\right)$ | | $70\lt Q_{\max}\le 80$ | $170-Q_{\max}$ | | $Q_{\max} \le 70$ | $100$ | 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: ```cpp sorting(6) ``` Your code may interact as follows: ```cpp 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: ```cpp 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