BOJ 24733 - 이것도 XOR해 보시지
$O(NK)$로 해결 가능하다.
$0$번째 수와 모든 수를 쿼리해서 $n-1$ 번의 쿼리를 써서 만든 배열을 $R$이라 하자.
$0$번째 수와 $\oplus$ 했을 때 $0$이 나오면 그것과 같다는 의미이다.
$k=1,2,\dots$ 을 반복하며 $t_0=k$ 로 두고 모든 다른 수를 $k \oplus R_i$ 를 해준다.
$R_i=a_0 \oplus a_i$ 이기 때문에 $k \oplus R_i = k \oplus k \oplus a_i=a_i$ 가 되기 때문이다.
이렇게 각 $k$마다 만들어진 배열을 $T$라 할 때,
$T$가 문제의 조건($1 \le p \le k$)에 맞게 수들이 배치가 되었는지 살핀다.
그렇다면 그것이 정답이고 아니라면 $k$를 계속 증가시킨다.
Comments