P15134 [ROIR 2026] XOR Coloring

Given two non-negative integer arrays $A=[a_1, a_2, \ldots, a_n]$ and $B=[b_1, b_2, \ldots, b_m]$. Define $S(i) = \{j | (a_i \oplus b_j) \leq x\}$. In other words, $S(i)$ is the set of indices $j$ in array $B$ such that the bitwise XOR of $a_i$ and $b_j$ is at most $x$. Find the minimum number $k$ such that the elements in array $A$ can be colored using $k$ colors, and the following condition holds: if $S(x)$ and $S(y)$ intersect, then $x$ and $y$ must be colored with different colors. That is, you need to find $c_1, c_2, \ldots, c_n$ such that $1 \le c_i \le k$, and if $S(x) \cap S(y) \neq \varnothing$, then $c_x \neq c_y$. As a reminder, the bitwise XOR ($\oplus$, xor) of two non-negative integers is defined as follows: write both numbers in binary, and the $i$-th bit of the result is 1 if and only if exactly one of the two numbers has a 1 in that bit. For example, $(14 \text{ xor } 7) = (1110_2 \oplus 0111_2) = 1001_2 = 9$. This operation is implemented in all modern programming languages: it is written as `^` in C++, Java, and Python, and as xor in Pascal.

The input contains multiple test cases. The first line contains an integer $t$ $(1 \le t \le 100)$, the number of test cases. The following lines describe the test cases. The first line of each test case contains three integers $n$, $m$, and $x$ ($1 \le n, m \le 500\,000$, $0 \leq x < 2^{30}$). The second line contains $n$ integers $a_1, a_2, \ldots, a_n$, the elements of array $A$ ($0 \le a_i < 2^{30}$). The third line contains $m$ integers $b_1, b_2, \ldots, b_m$, the elements of array $B$ ($0 \le b_i < 2^{30}$). It is guaranteed that the sum of $n$ over all test cases and the sum of $m$ over all test cases are both at most $500\,000$.

For each test case, output one integer, the required minimum $k$.

### Scoring Rules | Subtask | Points | Additional Constraints | Required Subtasks | |:-:|:-:|:-:|:-:| | 1 | 5 | $n \le 2$ | --- | | 2 | 5 | $n \le 5$ | 1 | | 3 | 5 | $n \le 15$ | 1, 2 | | 4 | 5 | $n \le 100$ | 1–3 | | 5 | 5 | $n \le 2\,000$ | 1–4 | | 6 | 10 | $n \le 5\,000$ | 1–5 | | 7 | 5 | $n \le 100\,000$，$m = 2$ | --- | | 8 | 10 | $n \leq 100\,000$，$m = 3$ | --- | | 9 | 5 | $n, m \le 100\,000$；$a_i, b_i, k < 2$ | --- | | 10 | 10 | $n, m \le 100\,000$；$a_i, b_i, k < 4$ | 9 | | 11 | 35 | No additional constraints. | 1–10 | Translated by ChatGPT 5