Codeforces Round 880 (Div. 1) |
---|
Закончено |
Известный во всем мире астрофизик Млейл ваГрасс Тайсок недавно прочитал о существовании скоплений галактик-близнецов. Прежде чем поделиться этими знаниями с широкой аудиторией в своем подкасте под названием S.tarT-ok, он хочет доказать их существование самостоятельно. Млейл осознает, что просторы Вселенной поражают воображение (почти так же поражают, как и его наблюдательность), и решает попытать счастья и найти новое скопление галактик-близнецов.
Для этого он использует свой ТЛескоп для наблюдения за еще не исследованной человечеством частью ночного неба, в которой есть ровно $$$2^{k + 1}$$$ галактик, расположенных в ряд. $$$i$$$-я из них состоит ровно из $$$0 \le g_i < 4^k$$$ звезд.
Скопление галактик — это любой непустой непрерывный подотрезок галактик. Более того, считается, что её признак равен побитовому исключающему ИЛИ всех значений $$$g_i$$$ в этом диапазоне.
Два скопления галактик считаются близнецами тогда и только тогда, когда они имеют равные признаки и их соответствующие отрезки не пересекаются.
Напишите программу, которая для многих сценариев будет читать описание участка ночного неба, наблюдаемого Млейлем, и выводить расположение двух отрезков, принадлежащих некоторой паре галактик-близнецов, или единственное значение $$$-1$$$, если такой пары не существует.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$k$$$ ($$$0 \le k \le 17$$$).
Вторая строка содержит $$$2^{k + 1}$$$ целых чисел $$$g_1, g_2, \ldots, g_{2^{k+1}}$$$ ($$$0 \le g_i < 4^k$$$).
Гарантируется, что сумма значений $$$2^{k + 1}$$$ по всем наборам входных данных не превосходит $$$2^{18}$$$.
Ответы для всех наборов входных данных должны содержаться в отдельных строках. Если существует пара галактик-близнецов, то выведите четыре целых числа $$$a$$$, $$$b$$$, $$$c$$$ и $$$d$$$, обозначающие их отрезки $$$[a, b]$$$ и $$$[c, d]$$$ (первый интервал не обязан начинаться раньше второго, но они должны быть непересекающимися). Если пары таких галактик не существует, выведите единственное значение $$$-1$$$.
424 15 0 7 11 8 3 210 1 2 300 0315 63 57 39 61 25 42 61 50 41 27 41 56 23 17 27
2 4 6 6 2 2 3 4 1 1 2 2 1 1 4 10
В первом наборе входных данных мы выбираем интервалы $$$[2, 4]$$$ и $$$[6, 6]$$$ в качестве наших галактик-близнецов. Признак первого интервала равен $$$15 \oplus 0 \oplus 7 = 8$$$, и признак второго интервала равен $$$8$$$, так что эти скопления галактик действительно являются близнецами.
Название |
---|