지저분한 버그 풀기

Ilshat은 효율적인 자료구조를 다루는 소프트웨어 엔지니어다. 어느 날 그는 새로운 자료구조를 고안했다. 이 자료구조는 $n$비트의 음이 아닌 정수 집합을 저장할 수 있다. 여기서 $n$은 2의 거듭제곱이다. 즉 $n = 2^b$를 만족하는 음이 아닌 정수 $b$가 있다.

자료구조는 처음에 비어 있다. 이 자료구조를 사용하는 프로그램은 다음 규칙을 따라야 한다.

• 프로그램은 add_element(x)로 $n$비트 정수를 하나씩 추가할 수 있다. 이미 집합에 있는 원소를 추가하면 아무 일도 일어나지 않는다.
• 마지막 원소를 추가한 뒤에는 compile_set()을 정확히 한 번 호출해야 한다.
• 마지막으로 프로그램은 check_element(x)를 호출해 원소 $x$가 집합에 있는지 확인할 수 있다. 이 함수는 여러 번 호출할 수 있다.

Ilshat은 이 자료구조를 처음 구현할 때 compile_set()에 버그를 넣었다. 이 버그는 모든 원소의 이진수 자릿수를 같은 방식으로 재배열한다. Ilshat은 버그가 적용하는 재배열을 정확히 찾고 싶어 한다.

형식적으로 설명하면 다음과 같다. $0$부터 $n-1$까지의 수가 각각 정확히 한 번씩 나타나는 수열 $p = [p_0, \ldots, p_{n-1}]$을 생각하자. 이런 수열을 순열이라고 한다. 이진수 자릿수가 $a_0, \ldots, a_{n-1}$인 원소를 생각하자(단, $a_0$이 최상위 비트다). compile_set()이 호출되면 이 원소는 자릿수가 $a_{p_0}, a_{p_1}, \ldots, a_{p_{n-1}}$인 원소로 바뀐다. 모든 원소에 같은 순열 $p$가 적용된다. 어떤 순열이든 가능하며, 모든 $0 \le i \le n-1$에 대해 $p_i = i$인 항등 순열도 포함된다.

예를 들어 $n = 4$이고 $p = [2, 1, 3, 0]$이라고 하자. 집합에 이진 표기가 0000, 1100, 0111인 정수를 넣었다면, compile_set 호출 후 이 원소들은 각각 0000, 0101, 1110이 된다.

프로그램은 자료구조와 상호작용하여 순열 $p$를 찾아야 한다. 다음 순서로 진행한다.

1. $n$비트 정수들의 집합을 고른다.
2. 그 정수들을 자료구조에 넣는다.
3. compile_set을 호출해 버그를 발생시킨다.
4. 수정된 집합에 일부 원소가 있는지 확인한다.
5. 그 정보로 순열 $p$를 알아내어 반환한다.

compile_set은 한 번만 호출할 수 있다.

라이브러리 함수 호출 횟수에도 제한이 있다. 프로그램은 다음 한도 안에서 호출할 수 있다.

• add_element는 최대 $w$번 호출할 수 있다. ($w$는 "writes"의 약자다.)
• check_element는 최대 $r$번 호출할 수 있다. ($r$은 "reads"의 약자다.)