Given 2 integers $u$ and $v$, find the shortest array such that bitwise-xor of its elements is $u$, and the sum of its elements is $v$.
Input
The only line contains 2 integers $u$ and $v$ $(0 \le u,v \le 10^{18})$.
Output
If there’s no array that satisfies the condition, print “-1”. Otherwise:
The first line should contain one integer, $n$, representing the length of the desired array. The next line should contain $n$ positive integers, the array itself. If there are multiple possible answers, print any.
Examples
input
2 4
output
2 3 1
input
1 3
output
3 1 1 1
input
8 5
output
-1
input
0 0
output
0
Note
In the first sample, $3\oplus 1 = 2$ and $3 + 1 = 4$. There is no valid array of smaller length.
Notice that in the fourth sample the array is empty.
Solution:
#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(random_device{}()); const ll mod=1000000007; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head ll u,v; int main() { scanf("%lld%lld",&u,&v); if ((v-u)%2!=0) { puts("-1"); return 0; } if (u>v) { puts("-1"); return 0; } if (u==0&&v==0) { puts("0"); return 0; } if (u==v) { puts("1"); printf("%lld\n",u); return 0; } ll p=(v-u)/2; ll q=u^p; if (p+q==v) { puts("2"); printf("%lld %lld\n",p,q); return 0; } puts("3"); printf("%lld %lld %lld\n",u,(v-u)/2,(v-u)/2); }
Related posts:
PE Lesson
Encoding
Banana
Underfail
New Year and Binary Tree Paths
Cow and Treats
Race
Zip-line
Felicity is Coming!
Book of Evil
Nested Rubber Bands
Long number
Search for a pair of intersecting segments
Generating all $K$-combinations
Makoto and a Blackboard
Pearls in a Row
Grandfather Dovlet’s calculator
Ehab and Path-etic MEXs
Exercising Walk
Package Delivery
Lingua Romana
Graph Reconstruction
Một số vấn đề đáng chú ý trong môn Tin học - Phan Công Minh
Orac and LCM
Scheduling jobs on one machine
Dome
Length of the union of segments
Obsessive String
Dynamic Programming on Broken Profile
Fence
Escaping on Beaveractor
Cow and Snacks