| VK Cup 2018 - Раунд 1 |
|---|
| Закончено |
У Алисы есть важное сообщение M, состоящее из нескольких неотрицательных целых чисел, которое она хочет сохранить в тайне от Евы. Алиса знает, что единственный теоретически защищенный способ шифрования — использование одноразового ключа. Алиса сгенерировала случайный ключ K с длиной, равной длине сообщения. Алиса затем вычислила побитовое исключающее ИЛИ каждого соответствующего элемента массива и ключа (
, где 
обозначает операцию побитового исключающего ИЛИ) и сохранила зашифрованное сообщение A. Алиса умная. Будь как Алиса.
Например, пусть Алиса хочет сохранить сообщение M = (0, 15, 9, 18), и она сгенерировала ключ K = (16, 7, 6, 3). Тогда зашифрованное сообщение равно A = (16, 8, 15, 17).
Алиса понимает, что она не может хранить ключ вместе с зашифрованным сообщением. Поэтому Алиса послала ключ K Бобу и удалила свою копию. Алиса умная. Действительно, будь как Алиса.
Боб понимает, что зашифрованное сообщение защищено только до тех пор, пока ключ является секретным. Поэтому Боб случайным образом поменял местами элементы ключа перед тем, как сохранить его. Боб думает, что в таком случае, даже если Ева получит и зашифрованное сообщение, и ключ, она не сможет прочитать исходное сообщение. Боб не умный. Не будь как Боб.
В примере выше Боб мог, например, выбрать перестановку (3, 4, 1, 2), перемешать элементы в соответствии с ней и сохранить ключ P = (6, 3, 16, 7).
Прошел год, и Алиса теперь хочет расшифровать свое сообщение. Только сейчас Боб понял, что это невозможно. Так как он поменял местами элементы ключа случайным образом, сообщение утеряно навсегда. Мы уже сказали, что Боб не очень умный?
Боб хочет получить хотя бы какую-то информацию из сообщения. Так как он не очень умный, он попросил у вас помощи. Вам известны зашифрованное сообщение A и произвольно перемешанный ключ P. Каково лексикографически минимальное сообщение, которое могло быть зашифровано подобным образом?
Формально, по данным A и P найдите лексикографически минимальное сообщение O такое, что существует перестановка π такая, что 
для всех i.
Напомним, что последовательность S лексикографически меньше последовательности T, если существует такая позиция i, что Si < Ti, а для всех j < i выполняется Sj = Tj.
Первая строка содержит одно целое число N (1 ≤ N ≤ 300000) — длину сообщения.
Вторая строка содержит N целых чисел A1, A2, ..., AN (0 ≤ Ai < 230) — зашифрованное сообщение.
Третья строка содержит N целых чисел P1, P2, ..., PN (0 ≤ Pi < 230) — ключ шифрования, элементы которого переставлены произвольным образом.
Выведите одну строку с N целыми числами — лексикографически минимально возможное сообщение O. Напомним, что все числа в нем должны быть неотрицательны.
3
8 4 13
17 2 7
10 3 28
5
12 7 87 22 11
18 39 9 12 16
0 14 69 6 44
10
331415699 278745619 998190004 423175621 42983144 166555524 843586353 802130100 337889448 685310951
226011312 266003835 342809544 504667531 529814910 684873393 817026985 844010788 993949858 1031395667
128965467 243912600 4281110 112029883 223689619 76924724 429589 119397893 613490433 362863284
В первом примере решением является (10, 3, 28), потому что 
, 
и 
. Другие возможные перестановки ключа дают сообщения (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, 15) и (15, 6, 28), все из которых лексикографически больше, чем оптимальное решение.
