| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 78 | 69 | 53 | 91.379% |
1ドル$부터 $N$까지의 정수로 이루어진 길이 $N$의 순열 $P$가 있다. 배열 $A_{i}$는 $P$의 처음 $i(1≤i≤N)$개의 원소를 정렬시킨 길이 $i$의 배열로 정의한다. 배열 $B$는 $A_{1} \oplus A_{2} \oplus \cdots \oplus A_{N-1} \oplus A_{N} \oplus P$ 연산을 수행한 새로운 배열로 정의한다. 두 배열의 xor 연산은 아래의 절차로 이루어진다.
1. 두 배열의 길이가 같다면 다음과 같이 연산한다.
$ A \oplus B = [ A_{1} \oplus B_{1}, A_{2} \oplus B_{2}, \cdots , A_{N-1} \oplus B_{N-1}, A_{N} \oplus B_{N} ] $
2. 길이가 $N$인 배열 $A$와 길이가 $M$인 배열 $B$가 있는 경우 다음과 같이 연산한다. ( $N < M$ )
$A \oplus B = [ A_{1} \oplus B_{1}, A_{2} \oplus B_{2}, \cdots , A_{N-1} \oplus B_{N-1}, A_{N} \oplus B_{N}, B_{N+1} , \cdots , B_{M-1}, B_{M} ] $
배열 $B$가 주어졌을 때 원래 순열 $P$를 구하는 프로그램을 작성하시오.
여기서 $\oplus$는 bitwise xor 연산을 의미한다. bitwise xor 연산의 정의는 하단 힌트 탭에 있다.
첫째 줄에 순열의 길이 $N$이 주어진다. $ \left( 1 \leq N \leq 5,000円 \right) $
둘째 줄에 배열의 원소 $B_{i}$가 공백으로 구분되어 주어진다.
순열 $P$로 복원할 수 있는 배열 $B$만 주어지며 $B_{i}$는 항상 2ドル^{31}$보다 작은 음이 아닌 정수다.
첫째 줄에 순열 $P$의 원소를 공백으로 구분해 출력한다.
3 0 2 0
1 2 3
4 0 6 5 5
4 3 2 1
$P = \left[ 4, 3, 2, 1 \right]$
$A_{1} = \left[ 4 \right]$
$A_{2} = \left[ 3, 4 \right]$
$A_{3} = \left[ 2, 3, 4 \right]$
$A_{4} = \left[ 1, 2, 3, 4 \right]$
$B = A_{1} \oplus A_{2} \oplus A_{3} \oplus A_{4} \oplus P = \left[ 4 \oplus 3 \oplus 2 \oplus 1 \oplus 4, 4 \oplus 3 \oplus 2 \oplus 3, 4 \oplus 3 \oplus 2, 4 \oplus 1 \right] = \left[ 0, 6, 5, 5 \right]$
bitwise xor 연산은 두 개의 2진수 값에 대해 자리 단위로 적용되는 연산이다. 먼저 피연산자로 주어진 두 값을 2진수로 표현한다. 그 뒤에 두 값의 각 자릿수를 비교해, 두 값이 다르면 1, 두 값이 같으면 0으로 계산한다.
예를 들어 12ドル \oplus 6$의 값은 10ドル$이다. 12ドル$는 2진수로 표현하면 1100ドル_{(2)}$이고 6ドル$은 2진수로 표현하면 0110ドル_{(2)}$이다. xor 연산은 아래의 그림과 같이 진행되고 결과는 1010ドル_{(2)},ドル 즉 10ドル$이다.