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: