|
XOR Раскраска
(Время: 3 сек. Память: 256 Мб Сложность: 80%)
Даны два массива неотрицательных целых чисел A = [a₁, a₂, ..., aₙ] и B = [b₁, b₂, ..., bₘ].
Пусть S(i) = {j | (aᵢ ⊕ bⱼ) ≤ x}. То есть S(i) это множество всех индексов j массива B, для которых побитовое исключающее или aᵢ и bⱼ не превосходит x.
Требуется найти минимальное число k, чтобы можно было покрасить элементы массива A в k цветов таким образом, что если S(x) и S(y) пересекаются, то x и y покрашены в разный цвет.
Иначе говоря, можно найти такие c1, c1, ..., cn, что 1 ≤ ci ≤ k, и при этом если S(x) ∩ S(y) ≠ ∅, то cx ≠ cy.
Напомним, что побитовое «исключающее или» (⊕, xor) двух целых неотрицательных чисел определяется следующим образом: запишем оба числа в двоичной системе счисления, i-й двоичный разряд результата равен 1, если ровно у одного из аргументов он равен 1. Например, (14 xor 7) = (11102 ⊕ 01112) = 10012 = 9. Эта операция реализована во всех современных языках программирования, в языках C++, Java и Python она записывается как «ˆ», в Паскале как «xor».
Входные данные
Первая строка входного файла INPUT.TXT содержит одно целое число t (1 ≤ t ≤ 100) – количество тестовых примеров.
Далее следуют описания тестовых примеров. В первой строке каждого теста записаны три целых числа n, m и x (1 ≤ n, m ≤ 500000, 0 ≤ x < 230).
Во второй строке записаны n целых чисел a₁, a₂, ..., aₙ (0 ≤ aᵢ < 230).
В третьей строке записаны m целых чисел b₁, b₂, ..., bₘ (0 ≤ bᵢ < 230).
Выходные данные
В выходной файл OUTPUT.TXT для каждого тестового примера выведите одно целое число – минимальное искомое k.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
2 2 0
0 0
1 1
5 5 3
0 1 2 3 4
0 1 2 3 4
5 5 4
0 1 2 3 4
0 1 2 3 4 | 1
4
5 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
