Олимпиадный тренинг

Задача . E. Распределение XOR


Задача

Темы: битмаски жадные алгоритмы Конструктив математика *2100

Вам дан массив из ровно \(n\) чисел \([1,2,3,\ldots,n]\), а также целые числа \(k\) и \(x\).

Вам нужно разбить массив на ровно \(k\) непустых непересекающихся подпоследовательностей так, чтобы побитовое исключающее ИЛИ всех чисел в каждой подпоследовательности было равно \(x\), и каждое число находилось ровно в одной подпоследовательности. Обратите внимание, что нет никаких ограничений на длину каждой подпоследовательности.

Последовательность \(a\) является подпоследовательностью \(b\), если \(a\) может быть получена из \(b\) удалением нескольких (возможно, ни одного или всех) элементов.

Например, для \(n = 15\), \(k = 6\), \(x = 7\) корректно следующее разбиение:

  • \([6,10,11]\), \(6 \oplus 10 \oplus 11 = 7\),
  • \([5,12,14]\), \(5 \oplus 12 \oplus 14 = 7\),
  • \([3,9,13]\), \(3 \oplus 9 \oplus 13 = 7\),
  • \([1,2,4]\), \(1 \oplus 2 \oplus 4 = 7\),
  • \([8,15]\), \(8 \oplus 15 = 7\),
  • \([7]\), \(7 = 7\),
где \(\oplus\) обозначает операцию побитового исключающего ИЛИ.

Следующее разбиение некорректно, так как не используются числа \(8\) и \(15\):

  • \([6,10,11]\), \(6 \oplus 10 \oplus 11 = 7\),
  • \([5,12,14]\), \(5 \oplus 12 \oplus 14 = 7\),
  • \([3,9,13]\), \(3 \oplus 9 \oplus 13 = 7\),
  • \([1,2,4]\), \(1 \oplus 2 \oplus 4 = 7\),
  • \([7]\), \(7 = 7\).

Следующее разбиение некорректно, так как \(3\) встречается дважды, а \(1\), \(2\) не используются:

  • \([6,10,11]\), \(6 \oplus 10 \oplus 11 = 7\),
  • \([5,12,14]\), \(5 \oplus 12 \oplus 14 = 7\),
  • \([3,9,13]\), \(3 \oplus 9 \oplus 13 = 7\),
  • \([3,4]\), \(3 \oplus 4 = 7\),
  • \([8,15]\), \(8 \oplus 15 = 7\),
  • \([7]\), \(7 = 7\).
Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит три целых числа \(n\), \(k\), \(x\) (\(1 \le k \le n \le 2 \cdot 10^5\); \(1\le x \le 10^9\)) — длина массива, количество подпоследовательностей и требуемое значение XOR.

Гарантируется, что сумма \(n\) не превосходит \(2 \cdot 10^5\).

Выходные данные

Для каждого набора входных данных, если ответ существует, выведите «YES» в первой строке. В \(i\)-й из следующих \(k\) строк сначала выведите целое число \(s_i\) — длину \(i\)-й подпоследовательности, затем выведите \(s_i\) целых чисел — саму \(i\)-ю подпоследовательность. Если ответов несколько, выведите любой. Обратите внимание, что вы можете вывести элементы подпоследовательности в любом порядке.

В противном случае выведите «NO».

Примечание

В первом наборе входных данных мы строим следующие \(6\) подпоследовательностей:

  • \([6,10,11]\), \(6 \oplus 10 \oplus 11 = 7\),
  • \([5,12,14]\), \(5 \oplus 12 \oplus 14 = 7\),
  • \([3,9,13]\), \(3 \oplus 9 \oplus 13 = 7\),
  • \([1,2,4]\), \(1 \oplus 2 \oplus 4 = 7\),
  • \([8,15]\), \(8 \oplus 15 = 7\),
  • \([7]\), \(7 = 7\).

Во втором наборе входных данных мы строим следующие \(4\) подпоследовательности:

  • \([1,4]\), \(1 \oplus 4 = 5\),
  • \([2,7]\), \(2 \oplus 7 = 5\),
  • \([3,6]\), \(3 \oplus 6 = 5\),
  • \([5,8,9,10,11]\), \(5 \oplus 8 \oplus 9 \oplus 10 \oplus 11 = 5\).

Следующей разбиение также будет считаться правильным в этом наборе входных данных:

  • \([1,4]\), \(1 \oplus 4 = 5\),
  • \([2,7]\), \(2 \oplus 7 = 5\),
  • \([5]\), \(5 = 5\),
  • \([3,6,8,9,10,11]\), \(3 \oplus 6 \oplus 8 \oplus 9 \oplus 10 \oplus 11 = 5\).

Примеры
№Входные данныеВыходные данные
1 7
15 6 7
11 4 5
5 3 2
4 1 4
6 1 7
11 5 5
11 6 5 
YES
3 6 10 11
3 5 12 14
3 3 9 13
3 1 2 4
2 8 15
1 7
YES
2 1 4
2 2 7
2 3 6
5 5 8 9 10 11
NO
YES
4 1 2 3 4
YES
6 1 2 3 4 5 6
NO
NO

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет