兼容数字(Compatible Numbers)

题目描述

如果两个整数 $x$ 和 $y$ 的按位与运算结果为 $0$，即 $x\ \&\ y=0$，那么它们是兼容的。例如，$90\ (1011010_2)$ 和 $36\ (100100_2)$ 是兼容的，因为 $1011010_2\ \&\ 100100_2=0_2$，而 $3\ (11_2)$ 和 $6\ (110_2)$ 则不兼容，因为 $11_2\ \&\ 110_2=10_2$。

给定一个整数数组 $a_1,a_2,\ldots,a_n$。你需要判断，对于每个数组元素，是否存在数组中的其它元素跟它兼容？如果存在兼容元素，还需要输出一个满足条件的元素。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 10^6$），表示数组的元素个数。第二行包含 $n$ 个用空格分隔的整数 $a_1,a_2,\ldots,a_n$（$1 \leq a_{i} \leq 4 \cdot 10^6$），表示数组元素。数组中的数字可以重复。

输出格式

输出 $n$ 个整数 $ans_1\ ans_2\ \ldots\ ans_n$。如果 $a_i$ 与数组 $a_1,a_2,\ldots,a_n$ 中不存在任何其它元素兼容，则 $ans_i$ 等于 $-1$。否则 $ans_i$ 是与 $a_i$ 兼容的任一数组中的元素，即满足 $a_i\ \&\ ans_i=0$，且 $ans_i$ 出现在数组中。

样例输入 #1

2
90 36

样例输出 #1

36 90

样例输入 #2

4
3 6 3 6

样例输出 #2

-1 -1 -1 -1

样例输入 #3

5
10 6 9 8 2

样例输出 #3

-1 8 2 2 8

数据范围

由 ChatGPT 5 翻译

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接