Perfect Security

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

예를 들어 Alice가 저장하려던 메시지는 M = (0, 15, 9, 18)이었을 수 있다. Alice는 키 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이 똑똑하지 않다고 말했던가?

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)이 나오며, 이들은 모두 답보다 사전순으로 크다.