首页 > 其他 > 详细

D. Ehab the Xorcist

时间:2020-04-11 15:45:35      阅读:49      评论:0      收藏:0      [点我收藏+]

D. Ehab the Xorcist

time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given 2 integers uu and vv, find the shortest array such that bitwise-xor of its elements is uu, and the sum of its elements is vv.

Input

The only line contains 2 integers uu and v(0u,v1018)(0≤u,v≤1018).

Output

If there‘s no array that satisfies the condition, print "-1". Otherwise:

The first line should contain one integer, nn, representing the length of the desired array. The next line should contain npositive integers, the array itself. If there are multiple possible answers, print any.

Examples
input
Copy
2 4
output
Copy
2
3 1
input
Copy
1 3
output
Copy
3
1 1 1
input
Copy
8 5
output
Copy
-1
input
Copy
0 0
output
Copy
0
Note

In the first sample, 31=23⊕1=2 and 3+1=43+1=4. There is no valid array of smaller length.

Notice that in the fourth sample the array is empty.

 

1.一个序列的异或和一定小于等于数值和。

2.一个序列的数值和和异或和奇偶性相同。

 

a+b=(ab)+2(ab)

 

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <map>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <deque>
#include <bitset>
//#include <unordered_set>
//#include <unordered_map>
//#include <bits/stdc++.h>
//#include <xfunctional>
#define ll  long long
#define PII  pair<int, int>
using namespace std;
int dir[5][2] = { { 0,1 } ,{ 0,-1 },{ 1,0 },{ -1,0 } ,{ 0,0 } };
const long long INF = 0x7f7f7f7f7f7f7f7f;
const int inf = 0x3f3f3f3f;
const double pi = 3.14159265358979;
const int mod = 1e9 + 7;
const int maxn = 2005;
//if(x<0 || x>=r || y<0 || y>=c)
//1000000000000000000

inline ll read()
{
    ll x = 0; bool f = true; char c = getchar();
    while (c < 0 || c > 9) { if (c == -) f = false; c = getchar(); }
    while (c >= 0 && c <= 9) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return f ? x : -x;
}

int main() 
{
    ll u, v;
    cin >> u >> v;
    ll d = v - u;
    if (d < 0 || (d % 2))
    {
        cout << -1 << endl;
        return 0;
    }
    if (!d)
    {
        if (!u)
            cout << 0 << endl;
        else
        {
            cout << 1 << endl;
            cout << u << endl;
        }
    }
    else
    {
        ll h = d >> 1;
        if ((h&u) == 0)
        {
            cout << 2 << endl;
            cout << h << " " << (h^u) << endl;
        }
        else
        {
            cout << 3 << endl;
            cout << h << " " << h << " " << u << endl;
        }
    }
    return 0;
}

 

D. Ehab the Xorcist

原文:https://www.cnblogs.com/dealer/p/12679694.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!