Codeforces

Luogu

分析

事实上有 $(a \operatorname{and} b) + (a \operatorname{or} b) = a + b$。那么
$$
b_i + c_i = na_i + \sum_{i = 1}^n a_i
$$
从而
$$
\sum_{i = 1}^n b_i + c_i = 2n\sum_{i = 1}^n a_i
$$
于是我们可以求出所有 $a_i$ 的和。这里注意判一下 $\sum b_i + c_i$ 是不是 $2n$ 的倍数。

接着我们就可以求出每个 $a_i$。这里也要注意判一下 $b_i + c_i - \sum a_i$ 是不是 $n$ 的倍数。

然后我们只需要检查求出的 $\{a_i\}$ 是否合法。我们对每一位算一下该位为 $1$ 的个数，即可对每个数 $\mathcal{O}(\log W)$ 求出 $b_i$ 和 $c_i$，然后判断是否相等即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 200000 + 10;

int n, a[N], b[N], c[N], o[31];

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) b[i] = read();
    for (int i = 1; i <= n; ++i) c[i] = read();
    ll s = 0;
    for (int i = 1; i <= n; ++i) s += b[i] + c[i];
    if (s % (n << 1)) { puts("-1"); return 0; }
    s /= (n << 1);
    for (int i = 1; i <= n; ++i) {
        if ((b[i] + c[i] - s) % n) { puts("-1"); return 0; }
        a[i] = (b[i] + c[i] - s) / n;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= 30; ++j)
            if (a[i] & (1 << j)) ++o[j];
    for (int i = 1; i <= n; ++i) {
        ll sa = 0, so = 0;
        for (int j = 0; j <= 30; ++j) {
            if (a[i] & (1 << j)) sa += 1ll * (1 << j) * o[j], so += 1ll * (1 << j) * n;
            else so += 1ll * (1 << j) * o[j];
        }
        if (sa != b[i] || so != c[i]) { puts("-1"); return 0; }
    }
    for (int i = 1; i <= n; ++i) printf("%d%c", a[i], " \n"[i == n]);
    return 0;
}