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:
Chain Reaction
Palisection
Weird Game
Petr and Permutations
Vanya and Exams
Fence Planks
Maximum flow - Push-relabel algorithm
Serega and Fun
Make Good
Desk Disorder
EKG
New Year and Ascent Sequence
Smallest Word
Josephus Problem
Dijkstra on sparse graphs
Kuroni and the Celebration
Decoding of Integer Sequences
Jerry's Protest
Gotta Catch Em' All!
New Year and Conference
Cách giải hay cho những bài toán trên vnspoj
Tricky Interactor
Color the Carpet
Bear and Destroying Subtrees
Egg Roulette
Letters and Question Marks
Numbers
4-point polyline
Barcode
Fast Fourier transform
Pearls in a Row
Startup Funding