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:
New Year and Forgotten Tree
Oriented area of a triangle
Design Tutorial: Learn from a Game
Magnum Opus
Rusty String
Hongcow's Game
Delaunay triangulation and Voronoi diagram
Hilbert's Hotel
Gennady and a Card Game
New Year Shopping
Birthday
Finding Power of Factorial Divisor
Jongmah
Bulbo
Maximum Xor Secondary
Definite Game
Dijkstra Algorithm
Round Marriage
No to Palindromes
Two Teams Composing
Placing Bishops on a Chessboard
Welfare State
Hongcow Buys a Deck of Cards
Aquarium decoration
Range Minimum Query
Cycles
Festival Organization
Game with Strings
Cartoons
Felicity is Coming!
Foo Fighters
Dreamoon Likes Strings