Codeforces Round 936 (Div. 2) |
---|
Закончено |
Совсем скоро у Ярика день рождения, и Марк решил подарить ему массив $$$a$$$ длины $$$n$$$.
Марк знает, что Ярик очень любит битовые операции, а также у него есть любимое число $$$x$$$, поэтому Марк хочет найти такое максимальное число $$$k$$$, что можно выбрать такие пары чисел [$$$l_1, r_1$$$], [$$$l_2, r_2$$$], $$$\ldots$$$ [$$$l_k, r_k$$$], что:
Если такого $$$k$$$ не существует, то нужно вывести $$$-1$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 10^5, 0 \le x < 2^{30}$$$) — длина массива $$$a$$$ и число $$$x$$$ соответственно.
Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — сам массив $$$a$$$.
Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Для каждого набора входных данных в отдельной строке выведите одно целое число — максимальное подходящее число $$$k$$$, и $$$-1$$$, если такого $$$k$$$ не существует.
83 11 2 32 21 12 21 32 30 03 20 0 14 21 3 3 72 22 35 00 1 2 2 1
2 2 1 2 3 -1 1 2
В первом наборе входных данных можно взять $$$k$$$ равным $$$2$$$ и выбрать два отрезка [$$$1, 1$$$] и [$$$2, 3$$$], $$$(1) | (2 \oplus 3) = 1$$$. Можно показать, что $$$2$$$ — максимальный возможный ответ.
Во втором наборе входных данных подходят отрезки [$$$1, 1$$$] и [$$$2, 2$$$], $$$(1) | (1) = 1$$$. Больше отрезков сделать нельзя.
В третьем наборе входных данных нельзя выбрать $$$2$$$ отрезка, так как $$$(1) | (3) = 3 > 2$$$, значит оптимальный ответ это $$$1$$$.
Название |
---|