[ABC281F] Xor Minimization
题意翻译
给定一个长度为 $N$ 的序列 $A$，求 $\min\limits^{\infty}_{i=0} \max\limits^N_{k=1} (A_k \oplus i)$，其中 $\oplus$ 是按位异或操作。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc281/tasks/abc281_f
非負整数列 $ A=(a_1,\ldots,a_N) $ が与えられます。
$ A $ に対して次の操作をちょうど $ 1 $ 回行います。
- 非負整数 $ x $ を選ぶ。そして、$ i=1,\ldots,N $ すべてに対し、$ a_i $ の値を「$ a_i $ と $ x $ のビット単位 xor」に置き換える。
操作後の $ A $ に含まれる値の最大値を $ M $ とします。$ M $ の最小値を求めてください。
ビット単位 xor とは 非負整数 $ A,\ B $ のビット単位 xor 、$ A\ \oplus\ B $ は、以下のように定義されます。 - $ A\ \oplus\ B $ を二進表記した際の $ 2^k $ ($ k\ \geq\ 0 $) の位の数は、$ A,\ B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $、そうでなければ $ 0 $ である。
例えば、$ 3\ \oplus\ 5\ =\ 6 $ となります (二進表記すると: $ 011\ \oplus\ 101\ =\ 110 $)。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ a_1 $ $ \ldots $ $ a_N $
输出格式
答えを出力せよ。
输入输出样例
输入样例 #1
3
12 18 11输出样例 #1
16输入样例 #2
10
0 0 0 0 0 0 0 0 0 0输出样例 #2
0输入样例 #3
5
324097321 555675086 304655177 991244276 9980291输出样例 #3
805306368说明
### 制約
- $ 1\ \leq\ N\ \leq\ 1.5\ \times\ 10^5 $
- $ 0\ \leq\ a_i\ \lt\ 2^{30} $
- 入力はすべて整数
### Sample Explanation 1
$ x=2 $ として操作をすると、操作後の数列は $ (12\ \oplus\ 2,18\ \oplus\ 2,\ 11\ \oplus\ 2)\ =\ (14,16,9) $ となり、最大値 $ M $ は $ 16 $ となります。 $ M $ を $ 16 $ より小さくすることは出来ないため、この値が答えです。