CF2162C.Beautiful XOR

普及-

通过率:0%

时间限制:2.00s

内存限制:256MB

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given two integers aa and bb. You are allowed to perform the following operation any number of times (including zero):

  • choose any integer xx such that 0≤x≤a0 \le x \le a (the current value of aa, not initial),
  • set a:=a⊕xa := a \oplus x. Here, ⊕\oplus represents the bitwise XOR operator.

After performing a sequence of operations, you want the value of aa to become exactly bb.

Find a sequence of at most 100100 operations (values of xx used in each operation) that transforms aa into bb, or report that it is impossible.

Note that you are not required to find the minimum number of operations, but any valid sequence of at most 100100 operations.

给你两个整数 aa 和 bb。你可以执行以下操作任意次(包括零次):

  • 任选一个整数 xx,满足 0≤x≤a0 \le x \le a(此处的 aa 是当前值,而非初始值);
  • 将 aa 更新为 a⊕xa \oplus x。其中 ⊕\oplus 表示按位异或运算符。

在执行一系列操作后,你希望 aa 的值恰好变为 bb。

请找出一个最多包含 100100 次操作的序列(即每次操作所用的 xx 值),使得 aa 被变换为 bb;若不可能实现,则报告无解。

注意:你无需找到操作次数最少的方案,只需给出任意一个长度不超过 100100 的合法操作序列即可。

输入格式

The first line of input contains a single integer tt (1≤t≤10001 \le t \le 1000) — the number of test cases.

Each test case contains two integers aa and bb (1≤a,b≤1091 \le a, b \le 10^9).

输入的第一行包含一个整数 tt(1≤t≤10001 \le t \le 1000)—— 表示测试用例的数量。

每个测试用例包含两个整数 aa 和 bb(1≤a,b≤1091 \le a, b \le 10^9)。

输出格式

For each test case, if it is impossible to obtain bb from aa using the allowed operations, print a single line containing −1-1.

Otherwise, on the first line print a single integer kk (0≤k≤1000 \le k \le 100) — the number of operations. On the second line print kk integers (x1,x2,…,xkx_1, x_2, \dots , x_k) — the chosen values of xx in the order you apply them.

If there are multiple valid sequences, you may print any one of them.

对于每个测试用例,如果无法通过允许的操作将 aa 变为 bb,则输出一行,包含 −1-1。

否则,在第一行输出一个整数 kk(0≤k≤1000 \le k \le 100)—— 表示操作次数;在第二行输出 kk 个整数(x1,x2,…,xkx_1, x_2, \dots , x_k)—— 表示按操作顺序所选取的 xx 值。

若存在多个合法的操作序列,输出任意一个即可。

输入输出样例

  • 输入#1

    6
    9 6
    13 13
    292 929
    405 400
    998 244
    244 353

    输出#1

    2
    7 8
    0
    -1
    1
    5
    2
    25 779
    -1

说明/提示

For the first test case,

  • choose x=7x = 7, now aa becomes equal to 9⊕7=149 \oplus 7 = 14.
  • choose x=8x = 8, now aa becomes equal to 14⊕8=614 \oplus 8 = 6.

Thus, we can make a=ba = b.

For the fourth test case, choosing x=5x = 5 makes a=ba = b.

对于第一个测试用例:

  • 选择 x=7x = 7,此时 aa 变为 9⊕7=149 \oplus 7 = 14。
  • 选择 x=8x = 8,此时 aa 变为 14⊕8=614 \oplus 8 = 6。

因此,我们可以使 a=ba = b。

对于第四个测试用例,选择 x=5x = 5 即可使 a=ba = b。

输入解题思路,AI测评打分。不知道怎么写?

首页