기계

시간 제한1초메모리 제한1024 MB

요약

기계에 배열 A를 넣으면 A[P[i]] XOR X 꼴의 배열 B가 나오므로, 알 수 없는 X 아래에서 사용 횟수 제한 안에 숨겨진 순열 P를 찾아야 합니다.

난이도: 보통10점 중 6점
유형: 비트 연산, 배열, 구현
정답자: 아직 제출이 없습니다

문제

고대 이집트의 컴퓨터 과학자들은 정수 배열을 섞는 기계를 여러 대 만들었다. 수천 년이 지나 고고학자들이 그중 한 대를 발견하고 조사했다.

이 기계는 정수 $N$ 개로 이루어진 배열 $A$ 를 입력으로 받는다. 기계에는 $0$ 부터 $N-1$ 까지 수의 내장 순열 $P$ 가 있고, 기계는 이것으로 배열을 섞는다. $P$ 는 길이가 $N$ 인 배열이며, $0$ 부터 $N-1$ 까지의 정수가 각각 정확히 한 번씩 나타난다.

기계는 부식 때문에 수를 섞기만 하는 것이 아니라, 각 수와 미지의 수 $X$ 의 XOR도 함께 계산한다. 기계는 길이가 $N$ 인 배열 $B$ 를 다음과 같이 돌려준다.

$B[i] = A[P[i]] \oplus X \quad (0 \le i < N)$

여기서 $\oplus$ 는 비트 단위 XOR 연산자다. 음이 아닌 정수 $c$ 와 $d$ 에 대해, $c \oplus d$ 의 $j$ 번째 비트는 $c$ 와 $d$ 의 $j$ 번째 비트가 서로 다를 때에만 1이다. $X$ 는 고정된 값이어서 기계를 여러 번 사용해도 바뀌지 않는다.

고고학자들이 알고 싶은 것은 내장 순열 $P$ 다. 기계를 사용해 $P$ 를 구하라. 각 부분 문제는 기계를 사용할 수 있는 횟수와 배열 $A$ 에 넣을 수 있는 가장 큰 수를 제한한다.

제한

$1 \le T \le 100$
$3 \le N \le 128$
$0 \le X \le 255$
각 $0 \le i < N$ 에 대해 $0 \le P[i] < N$
모든 $0 \le i < j < N$ 에 대해 $P[i] \ne P[j]$

예제1

예제 1
입력
```
1
3
0 0 0
0 1 2
```
예상 출력
```
0 1 2
```