Perfect Security

Alice에게는 Eve에게 비밀로 하고 싶은, 음이 아닌 정수 몇 개로 이루어진 매우 중요한 메시지 M가 있다. Alice는 이론적으로 안전한 유일한 암호가 일회용 패드라는 것을 알고 있다. Alice는 메시지와 길이가 같은 무작위 키 K를 생성한다. Alice는 메시지와 키의 각 원소에 대해 비트 단위 배타적 논리합을 계산하고(, 여기서 는 비트 단위 XOR 연산)을 나타낸다), 이렇게 암호화된 메시지 A를 저장한다. Alice는 똑똑하다. Alice처럼 행동하라.

예를 들어 Alice가 저장하려던 메시지는 M = (0, 15, 9, 18)이었을 수 있다. 그녀는 키 K = (16, 7, 6, 3)을 생성했다. 따라서 암호화된 메시지는 A = (16, 8, 15, 17)이다.

Alice는 암호화된 메시지와 함께 키를 저장할 수 없다는 것을 깨달았다. Alice는 자신의 키 K를 Bob에게 보내고 자신이 갖고 있던 사본을 삭제했다. Alice는 똑똑하다. 정말로 Alice처럼 행동하라.

Bob은 키가 비밀인 동안에만 암호화된 메시지가 안전하다는 것을 깨달았다. 따라서 Bob은 키를 저장하기 전에 무작위로 순열화했다. Bob은 이렇게 하면 Eve가 암호화된 메시지와 키를 모두 손에 넣더라도 메시지를 읽을 수 없을 것이라고 생각한다. Bob은 똑똑하지 않다. Bob처럼 행동하지 마라.

위 예제에서 Bob은 가령 순열 (3, 4, 1, 2)를 선택하고 순열화된 키 P = (6, 3, 16, 7)을 저장했을 수 있다.

한 해가 지나 Alice는 자신의 메시지를 복호화하려 한다. 이제야 Bob은 이것이 불가능하다는 것을 깨달았다. 키를 무작위로 순열화했으므로 메시지는 영원히 사라졌다. Bob이 똑똑하지 않다고 이미 말했던가?

Bob은 메시지에서 적어도 일부 정보라도 건져내고 싶어 한다. 그는 그다지 똑똑하지 않으므로 당신에게 도움을 요청한다. 암호화된 메시지 A와 순열화된 키 P가 주어진다. 주어진 암호문으로부터 나왔을 수 있는 사전순으로 가장 작은 메시지는 무엇인가?

더 정확히 말하면, 주어진 A and P에 대해 모든 i마다 를 만족하는 순열 π가 존재하도록 하는 사전순으로 가장 작은 메시지 O를 구한다.

어떤 인덱스 i가 존재하여 Si < Ti이고, 모든 j < i에 대해 조건 Sj = Tj가 성립하면 수열 S는 수열 T보다 사전순으로 작다는 점에 유의하라.

첫째 줄에 메시지의 길이를 나타내는 하나의 정수 N (1 ≤ N ≤ 300000)가 주어진다.

둘째 줄에는 암호화된 메시지를 나타내는 N개의 정수 A1, A2, ..., AN (0 ≤ Ai < 230)가 주어진다.

셋째 줄에는 순열화된 암호화 키를 나타내는 N개의 정수 P1, P2, ..., PN (0 ≤ Pi < 230)가 주어진다.

사전순으로 가장 작은 가능한 메시지 O를 나타내는 N개의 정수를 한 줄에 출력한다. 모든 원소는 음이 아니어야 한다는 점에 유의하라.

첫 번째 경우 답은 (10, 3, 28)이다. 이는 , , 이기 때문이다. 키의 다른 가능한 순열로 얻는 메시지는 (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, 15), (15, 6, 28)이며, 모두 답보다 사전순으로 더 크다.