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
Challenges in school №41
LCM Challenge
Z-function and its calculation
Beautiful Sequence
Maximums
Face Detection
Rabin-Karp Algorithm for string matching
Cow and Message
Reposts
Modular Multiplicative Inverse
Bad Ugly Numbers
New Year and Naming
Dijkstra on sparse graphs
Graph Decomposition
Deleting from a data structure in $O(T(n)\log n)$
Attack on Red Kingdom
Zuma
Parliament of Berland
Intersecting Subtrees
Playing on Graph
Integration by Simpson's formula
The Great Julya Calendar
Orac and Medians
Beautiful Mirrors with queries
Decoding of Integer Sequences
Giving Awards
Feed with Candy
Little Artem
Into Blocks (easy version)
Enduring Exodus
Aroma's Search