Задача №114789. Максимизировать сумму XOR
Будем обозначать как \(\oplus\) операцию побитового «исключающего или» для целых чисел. В языках программирования С++ и Java она обозначается символом « ^ », в паскале и Python — ключевым словом « xor ». Например, \(9 \oplus 3 = 1001_2 \oplus 11_2 = 1010_2 = 10\).
Даны два массива \(A\) и \(B\) длины \(n\). Обозначим как \(X(A)\) для массива \(A\) результат вычисления побитового «исключающего или» от всех элеметов массива: \(X(A) = A_1 \oplus A_2 \oplus \ldots \oplus A_n\). Аналогично, введем обозначение \(X(B) = B_1 \oplus B_2 \oplus \ldots \oplus B_n\).
Для каждого \(i\) от \(1\) до \(n\) разрешается поменять местами элементы \(A_i\) и \(B_i\). Необходимо определить, какие из этих обменов надо сделать, чтобы максимизировать сумму \(X(A) + X(B)\).
В первой строке входных данных находится число \(n\) — количество элементов (\(1 \le n \le {10}^5\)). В следующей строке находится \(n\) элементов массива \(A\) (\(0 \le A_i \le {10}^{18}\)). В следующей строке в таком же формате дан массив \(B\).
В первой строке выведите максимальную возможную сумму и число \(k\) — количество необходимых обменов. В следующей строке выведите \(k\) различных чисел от \(1\) до \(n\) — индексы элементов, которые надо поменять.
В примере после обмена массивы равны \(A = [2, 1]\) и \(B = [1, 2]\), соответственно.
\(X(A) = 2 \oplus 1 = 10_2 \oplus 1_2 = 11_2 = 3\), \(X(B) = 3\), \(X(A) + X(B) = 6\).
2 1 1 2 2
6 1 1