Codeforces Round 931 (Div. 2) |
---|
Закончено |
Это сольная версия задачи. Обратите внимание, что решение этой задачи может иметь или не иметь общих идей с решением игровой версии. Вы можете сдавать и получать баллы за каждую из версий независимо.
Вы можете делать взломы только тогда, когда обе версии задачи решены.
Дана целочисленная переменная $$$x$$$, которая изначально имеет значение $$$n$$$. Операция разбиения определена как:
Здесь $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.
В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq m \lt n \leq 10^{18}$$$) — изначальное значение $$$x$$$ и требуемое значение $$$x$$$.
Для каждого набора тестовых данных выведите ваш ответ в следующем формате.
Если невозможно достичь требуемого значения $$$m$$$ за $$$63$$$ операции, то выведите $$$-1$$$ в единственной строке.
Иначе,
Первая строка должна содержать целое число $$$k$$$ ($$$1 \leq k \leq 63$$$) — где $$$k$$$ является количеством произведенных операций.
Следующая строка должна содержать $$$k+1$$$ целое число — последовательность, в виде которой переменная $$$x$$$ изменяется с ходом операций разбиения. $$$1$$$-е и ($$$k+1$$$)-ое числа должны равняться $$$n$$$ и $$$m$$$ соответственно.
37 34 2481885160128643072 45035996273704960
1 7 3 -1 3 481885160128643072 337769972052787200 49539595901075456 45035996273704960
В первом тестовом случае $$$n = 7$$$, для первой операции $$$x = 7$$$, если мы выберем $$$y = 3$$$, тогда $$$(7 \oplus 3) \lt 7$$$, следовательно мы можем обновить $$$x$$$ сделав его равным $$$3$$$ уже на первой операции, чему и равно $$$m$$$.
Во втором тестовом случае $$$n = 4$$$, для первой операции $$$x = 4$$$.
Если мы выберем:
Следовательно мы не можем выполнить первую операцию и невозможно сделать $$$x = 2$$$.
Название |
---|