Perfect Security
Contest: VK Cup 2018 - Round 1
Difficulty rating: 1800
Tags: data structures, greedy, strings, trees

Alice has a very important message M consisting of some non-negative integers that she wants to keep secret from Eve. Alice knows that the only theoretically secure cipher is one-time pad. Alice generates a random key K of the length equal to the message's length. Alice computes the bitwise xor of each element of the message and the key ($$A_i := M_i \oplus K_i$$, where $$\bigcirc$$ denotes the bitwise XOR operation) and stores this encrypted message A. Alice is smart. Be like Alice.

For example, Alice may have wanted to store a message M = (0, 15, 9, 18). She generated a key K = (16, 7, 6, 3). The encrypted message is thus A = (16, 8, 15, 17).

Alice realised that she cannot store the key with the encrypted message. Alice sent her key K to Bob and deleted her own copy. Alice is smart. Really, be like Alice.

Bob realised that the encrypted message is only secure as long as the key is secret. Bob thus randomly permuted the key before storing it. Bob thinks that this way, even if Eve gets both the encrypted message and the key, she will not be able to read the message. Bob is not smart. Don't be like Bob.

In the above example, Bob may have, for instance, selected a permutation (3, 4, 1, 2) and stored the permuted key P = (6, 3, 16, 7).

One year has passed and Alice wants to decrypt her message. Only now Bob has realised that this is impossible. As he has permuted the key randomly, the message is lost forever. Did we mention that Bob isn't smart?

Bob wants to salvage at least some information from the message. Since he is not so smart, he asks for your help. You know the encrypted message A and the permuted key P. What is the lexicographically smallest message that could have resulted in the given encrypted text?

More precisely, for given A and P, find the lexicographically smallest message O, for which there exists a permutation π such that $$O_{i} \oplus \pi(P_{i}) = A_{i}$$ for every i.

Note that the sequence S is lexicographically smaller than the sequence T, if there is an index i such that Si < Ti and for all j < i the condition Sj = Tj holds.

Input format:
The first line contains a single integer N (1 ≤ N ≤ 300000), the length of the message.

The second line contains N integers A1, A2, ..., AN (0 ≤ Ai < 230) representing the encrypted message.

The third line contains N integers P1, P2, ..., PN (0 ≤ Pi < 230) representing the permuted encryption key.

Output format:
Output a single line with N integers, the lexicographically smallest possible message O. Note that all its elements should be non-negative.

Constraints:
Time limit: 3.5 s
Memory limit: 512.0 MB

Note:
In the first case, the solution is (10, 3, 28), since $$8 \oplus 2 = 10$$, $$4 \oplus 7 = 3$$ and $$13 \oplus 17 = 28$$. Other possible permutations of key yield messages (25, 6, 10), (25, 3, 15), (10, 21, 10), (15, 21, 15) and (15, 6, 28), which are all lexicographically larger than the solution.

Example input:
3
8 4 13
17 2 7

Example output:
10 3 28

Example input:
5
12 7 87 22 11
18 39 9 12 16

Example output:
0 14 69 6 44

Editorial:
We decrypt the message greedily, one number at a time. Note that $$f(X): X \oplus Y$$ is a bijection on non-negative integers. For that reason, there is always a unique number from the key that lexicographically minimises the string. We can always pick and remove that number, output its xor with the current number from the encrypted text.
It remains to show how to do the above faster than $${\mathcal{O}}(N^{2})$$. We build a trie on the numbers from the key, more precisely on their binary representation, starting from the most significant bit. To find the number Kj that minimises $$K_{j} \oplus A_{i}$$, one can simply search for Ai, bit by bit. That is, if the k-th most significant bit of Ai is 1, we try to follow the edge labelled 1, and 0 otherwise. If we always succeed in that, we have found Ai in the key multiset, and hence $$K_j \oplus A_i = 0$$, which is clearly minimal. If at some bit, we do not succeed, we select the other branch (that is, if k-th bit of Ai is 1, but there is no such number in the key set, we pick 0 instead and continue. This solution uses $${ \mathcal { O } } ( N W )$$ time, where W is the number of bits (here it is 30).
The same approach can be also implemented using multiset, which is probably faster to write, but has an extra $${\mathcal {O}}(\log N)$$ multiplicative factor, which may or may not fit into TL.