思路
高维前缀和
高维前缀和
把数的二进制看成一个集合，二进制的每一位为 \(1\) 为全集 \(V\)。
根据题目描述，若两数 \(a, b\) 相容，则 \(a \operatorname{and} b = 0\)，容易发现，\(b \in \complement_{V}a\)，所以我们只需要用高维前缀和处理出 \(\complement_{V}a\) 的一个元素即可。若没有元素，输出 -1 就行了。
点击查看代码
#include <iostream>
#include <cstdio>
using namespace std;
void RD() {}
template<typename T, typename... U> void RD(T &x, U&... arg) {
x = 0; int f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
x *= f; RD(arg...);
}
const int N = 1e6 + 5, B = (1 << 22) + 5;
#define LF(i, __l, __r) for (int i = __l; i <= __r; i++)
#define RF(i, __r, __l) for (int i = __r; i >= __l; i--)
int n, a[N];
int f[B];
int main() {
RD(n);
LF(i, 1, n) RD(a[i]), f[a[i]] = a[i];
LF(i, 0, (1 << 22) - 1) LF(j, 0, 21)
if ((i & (1 << j)) && f[i ^ (1 << j)]) f[i] = f[i ^ (1 << j)];
LF(i, 1, n) printf("%d ", f[((1 << 22) - 1) ^ a[i]] ? f[(1 << 22) - 1 ^ a[i]] : -1);
return 0;
}