## APIO '22 P3 - Perm

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types
Allowed languages
C++

The Pharaohs use the relative movement and gravity of planets to accelerate their spaceships. Suppose a spaceship will pass by planets with orbital speeds in order. For each planet, the Pharaohs scientists can choose whether to accelerate the spaceship using this planet or not. To save energy, after accelerating by a planet with orbital speed , the spaceship cannot be accelerated using any planet with orbital speed . In other words, the chosen planets form an increasing subsequence of . A subsequence of p is a sequence that's derived from by deleting zero or more elements of . For example , , , and are subsequences of , but is not.

The scientists have identified that there are a total of different ways a set of planets can be chosen to accelerate the spaceship, but they have lost their record of all the orbital speeds (even the value of ). However, they remember that is a permutation of . A permutation is a sequence containing each integer from to exactly once. Your task is to find one possible permutation of sufficiently small length.

You need to solve the problem for different spaceships. For each spaceship , you get an integer , representing the number of different ways a set of planets can be chosen to accelerate the spaceship. Your task is to find a sequence of orbital speeds with a small enough length such that there are exactly ways a subsequence of planets with increasing orbital speeds can be chosen.

#### Implementation Details

You should implement the following procedure:

vector<int> construct_permutation(long long k)

• : is the desired number of increasing subsequences.
• This procedure should return an array of elements where each element is between and inclusive.
• The returned array must be a valid permutation having exactly increasing subsequences.
• This procedure is called a total of times. Each of these calls should be treated as a separate scenario.

#### Constraints  for all 1. ( points) (for all ). If all permutations you used have length at most and are correct, you receive points, otherwise .
2. ( points) No additional constraints. For this subtask, let be the maximum permutation length you used in any scenario. Then, your score is calculated according to the following table:
Condition Score        #### Examples

##### Example 1

Consider the following call:

construct_permutation(3)


This procedure should return a permutation with exactly increasing subsequences. A possible answer is , which has (empty subsequence), and as increasing subsequences.

##### Example 2

Consider the following call:

construct_permutation(8)


This procedure should return a permutation with exactly increasing subsequences. A possible answer is .

• line : • line ( ): The sample grader prints a single line for each containing the return value of construct_permutation, or an error message if one has occurred.