32261번 - Machine 서브태스크다국어언어 제한함수 구현

문제

The ancient Egyptian computer scientists built several machines that shuffled arrays of integers. Thousands of years later, archaeologists discovered one of their machines and examined it.

The machine takes as input an array of $N$ integers and operates in a very predictable manner. It has a built-in permutation $P$ of numbers from 0ドル$ to $N - 1$ that it uses to shuffle the input array. Specifically, $P$ is an array of length $N$ containing each element between 0ドル$ and $N - 1$ (inclusive) exactly once.

Because of corrosion, the machine not only shuffles the numbers, but also takes their bitwise XOR with some unknown number $X$. More formally, the machine takes as input an array $A$ of length $N,ドル consisting of non-negative integers. Then, it returns another array $B$ of length $N$ such that $B[i] = A[P [i]] \oplus X$ (0ドル ≤ i < N$), where $\oplus$ denotes the bitwise XOR operator. Note that $X$ is a fixed number, which does not change when you use the machine.

The bitwise XOR of two non-negative integers $c$ and $d$ is computed as follows. Assume that $c$ and $d$ have at most $t$ bits in their binary representation, that is $\max(c, d) < 2^t$. Then $c \oplus d$ is a number $z$ whose $j$-th bit (0ドル ≤ j < t$) is 1ドル$ if and only if the $j$-th bit of $c$ and $d$ is different.

The archaeologists are interested in the built-in permutation $P$. Your task is to find $P$ by using the machine. The subtasks in this task impose limits on the number of times you can use the machine and the maximum number you can provide in array $A$.

구현 상세

You should implement the following procedure:

std::vector<int> find_permutation(int N)

• $N$ : the length of $P$ and the machine input and output.
• This procedure can be called multiple times in each test case. Each call is called a scenario.
• This procedure should return the built-in permutation $P$.

The above procedure can make calls to the following procedure:

std::vector<int> use_machine(std::vector<int> A)

• $A$: an array of length $N$ specifying the input to the machine.
• The elements of $A$ must be integers from 0ドル$ to 2ドル^{15} - 1 = 32767,ドル inclusive.
• This procedure returns an array $B$ such that $B[i] = A[P [i]] \oplus X$ (for all 0ドル ≤ i < N$).
• This procedure can be called at most 129ドル$ times in each scenario.

Let $T$ denote the number of scenarios in a test case. The grader calls the find_permutation procedure once for each scenario.

입력

출력

제한

• 1ドル ≤ T ≤ 100$
• 3ドル ≤ N ≤ 128$
• 0ドル ≤ X ≤ 255$
• 0ドル ≤ P [i] < N$ for each $i$ such that 0ドル ≤ i < N$
• $P [i] \ne P [j]$ (for all $i$ and $j$ such that 0ドル ≤ i < j < N$)

서브태스크

힌트

예제 1

Consider a scenario in which $P = [0, 1, 2, 3, 4]$ and $X = 3$. The procedure find_permutation is called in the following way:

find_permutation(5)

This procedure may call use_machine([6, 6, 2, 9, 5]), which returns $[5, 5, 1, 10, 6]$. At this point, it can be deduced that $X = 3$. The procedure may then call use_machine([1, 8, 4, 0, 4]), which returns $[2, 11, 7, 3, 7]$. At this point, $P$ can be deduced and so the procedure should return $[0, 1, 2, 3, 4]$. In this example, 2ドル$ calls are made to the use_machine procedure and the maximum number provided as input to this procedure is 9ドル$.

예제 2

Consider a scenario in which $P = [0, 4, 3, 1, 2]$ and $X = 8$. The procedure find_permutation is called in the following way:

find_permutation(5)

This procedure may call use_machine([0, 5, 1, 1, 2]), which returns $[8, 10, 9, 13, 9]$. Based on this output, $P$ can be deduced and so the procedure should return $[0, 4, 3, 1, 2]$. In this example, only 1ドル$ call is made to the use_machine procedure, and the maximum number given as input to the machine is 5ドル$.

샘플 그레이더

The sample grader input starts with a line containing a single integer $T$ followed by $T$ scenarios in the following format.

N X
P[0] P[1] ... P[N-1]

The sample grader writes the output of the $T$ scenarios, each in the following format.

S
R[0] R[1] ... R[S-1]
Q' M'

Here, $R$ is the array returned by find_permutation and $S$ is its length. $Q'$ is the number of calls to use_machine and $M'$ is the maximum number provided as input to any of the calls.

첨부

• machine.zip