A11290 | XOR Break — Solo Version
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
This is the solo version of the problem. Note that the solution of this problem may or may not share ideas with the solution of the game version. You can solve and get points for both versions independently.
You can make hacks only if both versions of the problem are solved.
Given an integer variable $x$ with the initial value of $n$ . A single break operation consists of the following steps:
- Choose a value $y$ such that $0 \lt y \lt x$ and $0 \lt (x \oplus y) \lt x$ .
- Update $x$ by either setting $x = y$ or setting $x = x \oplus y$ .
Determine whether it is possible to transform $x$ into $m$ using a maximum of $63$ break operations. If it is, provide the sequence of operations required to achieve $x = m$ .You don't need to minimize the number of operations.
Here $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
You can make hacks only if both versions of the problem are solved.
Given an integer variable $x$ with the initial value of $n$ . A single break operation consists of the following steps:
- Choose a value $y$ such that $0 \lt y \lt x$ and $0 \lt (x \oplus y) \lt x$ .
- Update $x$ by either setting $x = y$ or setting $x = x \oplus y$ .
Determine whether it is possible to transform $x$ into $m$ using a maximum of $63$ break operations. If it is, provide the sequence of operations required to achieve $x = m$ .You don't need to minimize the number of operations.
Here $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).
输入格式
The first line contains one positive integer $t$ ( $1 \le t \le 10^4$ ) — the number of test cases.
Each test case consists of a single line containing two integers $n$ and $m$ ( $1 \leq m \lt n \leq 10^{18}$ ) — the initial value of $x$ and the target value of $x$ .
Each test case consists of a single line containing two integers $n$ and $m$ ( $1 \leq m \lt n \leq 10^{18}$ ) — the initial value of $x$ and the target value of $x$ .
输出格式
For each test case, output your answer in the following format.
If it is not possible to achieve $m$ in $63$ operations, print $-1$ .
Otherwise,
The first line should contain $k$ ( $1 \leq k \leq 63$ ) — where $k$ is the number of operations required.
The next line should contain $k+1$ integers — the sequence where variable $x$ changes after each break operation. The $1$ -st and $k+1$ -th integers should be $n$ and $m$ , respectively.
If it is not possible to achieve $m$ in $63$ operations, print $-1$ .
Otherwise,
The first line should contain $k$ ( $1 \leq k \leq 63$ ) — where $k$ is the number of operations required.
The next line should contain $k+1$ integers — the sequence where variable $x$ changes after each break operation. The $1$ -st and $k+1$ -th integers should be $n$ and $m$ , respectively.
输入输出样例
输入 #1
3 7 3 4 2 481885160128643072 45035996273704960
输出 #1
1 7 3 -1 3 481885160128643072 337769972052787200 49539595901075456 45035996273704960
In the first test case $n = 7$ , for the first operation $x = 7$ if we choose $y = 3$ then $(7 \oplus 3) \lt 7$ , hence we can update $x$ with $3$ which is equal to $m$ .
In the second test case $n = 4$ , for the first operation $x = 4$ .
If we choose:
- $y = 1$ then $(4 \oplus 1) \gt 4$
- $y = 2$ then $(4 \oplus 2) \gt 4$
- $y = 3$ then $(4 \oplus 3) \gt 4$
Hence we can't do the first operation and it is impossible to make $x = 2$ .
In the second test case $n = 4$ , for the first operation $x = 4$ .
If we choose:
- $y = 1$ then $(4 \oplus 1) \gt 4$
- $y = 2$ then $(4 \oplus 2) \gt 4$
- $y = 3$ then $(4 \oplus 3) \gt 4$
Hence we can't do the first operation and it is impossible to make $x = 2$ .
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?
提交通过
评测结果:Accepted