Official
B - XOR Matching 2 Editorial by evima
Let \(\oplus\) denote the bitwise XOR.
When \(x\) is fixed, whether it is possible to permute \(b\) so that \(a_i \oplus b_i = x\) holds is equivalent to whether it is possible to permute \(b\) so that \(b\) matches \(c\) where \(c_i = a_i \oplus x\). We can check the latter in \(O(N \log N)\) time by sorting, for example.
As candidate values of \(x\), it is enough to try \(N\) values \(a_1 \oplus b_1, a_1 \oplus b_2, \ldots, a_1 \oplus b_N\).
The whole process to list all good integers takes \(O(N^{2} \log N)\) time, which is fast enough.
posted:
last update: