P8376 [APIO2022] Permutation

This problem only supports C++ submissions. When submitting, you do not need to include the `perm.h` header file. You only need to paste the content of `perm.h` from the attachment at the beginning of your code.

Pharaohs use the gravity of planets to accelerate spaceships. Suppose a spaceship will fly by $n$ planets in order with orbital speeds $p[0], p[1],\dots, p[n - 1]$. When flying by each planet, the Pharaoh scientists may choose whether to use it to accelerate the spaceship. To save energy, after the spaceship flies by a planet with orbital speed $p[i]$ and accelerates, it can no longer accelerate when later flying by a planet with orbital speed $p[j] < p[i]$. In other words, the planets chosen for acceleration form an **increasing subsequence** of $p[0], p[1],\dots, p[n - 1]$. A subsequence of $p$ is a sequence obtained by deleting zero or more elements from $p$. For example, $[0]$, $[ ]$, $[0, 2]$, and $[0, 1, 2]$ are subsequences of $[0, 1, 2]$, but $[2, 1]$ is not. The scientists have confirmed that there are a total of $k$ different ways to choose planets to accelerate the spaceship, but they have lost the record of orbital speeds (even the value of $n$). However, they remember that $(p[0], p[1],\dots, p[n - 1])$ is a permutation of $0, 1,\dots, n - 1$. Here, a permutation is a sequence that contains every integer from $0$ to $n - 1$ exactly once. Your task is to find such a permutation $(p[0], p[1],\dots, p[n - 1])$ with the smallest possible length that satisfies the requirement. You need to solve this problem for $q$ different spaceships. For each spaceship $i$, you are given an integer $k_i$, which is the number of different ways to choose planets to accelerate the spaceship. Your task is to find an orbital speed sequence of sufficiently small length $n$, such that there are exactly $k_i$ increasing subsequences that can be chosen from it. ## Implementation Details You need to implement the following function: ```cpp int[] construct_permutation(int64 k) ``` - $k$ is the required number of increasing subsequences. - The function should return an array of $n$ elements, where each element is a number between $0$ and $n - 1$ (inclusive). - The returned array must be a valid permutation with exactly $k$ increasing subsequences. - This function will be called a total of $q$ times. Each call is considered an independent scenario.

The sample grader reads input in the following format: - Line $1$: $q$. - Line $2+i$ ($0\le i\le q-1$): $k_i$.

For each $k_i$, the sample grader prints one line containing the return value of the corresponding `construct_permutation` call. If an error occurs, it prints an error message.

## Examples ### Example $1$ Consider the following call: ```cpp construct_permutation(3) ``` The function should return a permutation that has exactly $3$ increasing subsequences. One possible answer is $[1,0]$, whose increasing subsequences are $[]$ (the empty subsequence), $[0]$, and $[1]$. ### Example $2$ Consider the following call: ```cpp construct_permutation(8) ``` The function should return a permutation that has exactly $8$ increasing subsequences. One possible answer is $[0,1,2]$. ## Constraints - $1\le q\le 100$. - $2\le k_i\le 10^{18}$ (for all $0\le i\le q-1$). ## Subtasks 1. ($10$ points) $2\le k_i\le 90$ (for all $0\le i\le q-1$). If all permutations you output have length at most $90$ and are correct, you will get $10$ points; otherwise, you will get $0$ points. 2. ($90$ points) No additional constraints. For this subtask, let $m$ be the maximum length among the permutations you output across all scenarios. Your score is computed according to the table below: |Condition|Score| |:-:|:-:| |$m\le 90$|$90$| |$90 < m\le 120$|$90-\dfrac{m-90}{3}$| |$120 < m\le 5000$|$80-\dfrac{m-120}{65}$| |$m > 5000$|$0$| # Input Format # Output Format # Hint Translated by ChatGPT 5