答えについて二分探索をします。

関数 \(f\)、\(g\)、\(f_d\)、\(g_d\) を以下のように定義します。

• 数列 \(C\) を適切に並べ替えることにより \(C_1 \oplus C_2, C_3 \oplus C_4, \ldots, C_{2k-1} \oplus C_{2k}\) をすべて \(x\) 以上にすることができる最大の \(k\) を \(f(C,x)\) とする。

• 数列 \(C\)、\(D\) を適切に並べ替えることにより \(C_1 \oplus D_1, C_2 \oplus D_2, \ldots, C_k \oplus D_k\) をすべて \(x\) 以上にすることができる最大の \(k\) を \(g(C,D,x)\) とする。

• 数列 \(C\) の各要素 \(i\) を \(i \bmod 2^{d+1}\) に置き換えた数列を \(C'\)、\(x' \coloneqq x \bmod 2^{d+1}\) として、\(f_d(C,x) \coloneqq f(C',x')\) とする。

• 数列 \(C\) の各要素 \(i\) を \(i \bmod 2^{d+1}\) に置き換えた数列を \(C'\)、数列 \(D\) の各要素 \(i\) を \(i \bmod 2^{d+1}\) に置き換えた数列を \(D'\)、\(x' \coloneqq x \bmod 2^{d+1}\) として \(g_d(C,D,x) \coloneqq g(C', D', x')\) とする。

直感的には、\(f_d\) や \(g_d\) を考える際には \(2^{d+1}\) 以上の位を切り捨てているなどと捉えることができます。

\(f(A,x) \geq \lfloor \frac{N+1}{2} \rfloor\) か？という判定問題が解ければよいです。

\(f(A,x) = f_{29}(A,x)\) であるため、\( f_{29}(A,x)\) を求めます。

実は、\(f_d(C,x)\) や \(g_d(C,D,x)\) の値はいくつかの点での \(f_{d-1}\) や \(g_{d-1}\) の値から再帰的に求めることができます。 以下、この再帰について詳しく説明します。以下、数列 \(X\) に対しその数列の長さを \(|X|\) というように表記します。

1 . \(f_d(C,x)\) を求める

説明の簡略化のため、\(C\) の各要素および \(x\) は \(0\) 以上 \(2^{d+1}\) 未満とします。

また、\(d \geq 0\) のとき \(C\) の要素のうち、\(2^d\) の位が \(0\) であるようなもののみからなる数列を \(C^{(0)}\)、\(2^d\) の位が \(1\) であるようなもののみからなる数列を \(C^{(1)}\) とします。

1-1. \(d = -1\) のとき

\(f_d(C,x) = \lfloor \frac{|C|}{2} \rfloor\) です（これが再帰の base case となります）。

1-2. \(d \geq 0\) で、\(x\) の \(2^d\) の位が \(0\) のとき

対称性より\(|C^{(0)}| \leq |C^{(1)}|\) の場合について考えれば十分です。 \(C^{(0)}\) の要素と \(C^{(1)}\) の要素の xor は必ず \(2^d\) 以上となり、\(2^d > x\) より \(x\) 以上にもなります。したがって、\(f_d(C,x) = |C^{(0)}| + \min (\lfloor \frac {(|C^{(1)}| - |C^{(0)}|)}{2} \rfloor, f_{d-1}(C^{(1)}, x))\) です（\(C^{(0)}\) の要素と \(C^{(1)}\) の要素からなるペアを貪欲に作ってよく、ここから従います)。

1-3. \(d \geq 0\) で、\(x\) の \(2^d\) の位が \(1\) のとき

\(C^{(0)}\) の要素どうしおよび \(C^{(1)}\) の要素どうしの xor は必ず \(2^d\) 未満となり、\(2^d \leq x\) より \(x\) 未満にもなります。したがって、\(f_d(C,x) = g_{d-1}(C^{(0)}, C^{(1)}, x)\) です。

2 . \(g_d(C,D,x)\) を求める

\(f_d(C,D,x)\) とほぼ同様に求めることができます。

説明の簡略化のため、\(C,D\) の各要素および \(x\) は \(0\) 以上 \(2^{d+1}\) 未満とします。

\(d \geq 0\) のとき \(C\) の要素のうち、\(2^d\) の位が \(0\) であるようなもののみからなる数列を \(C^{(0)}\)、\(2^d\) の位が \(1\) であるようなもののみからなる数列を \(C^{(1)}\)、\(D\) の要素のうち、\(2^d\) の位が \(0\) であるようなもののみからなる数列を \(D^{(0)}\)、\(2^d\) の位が \(1\) であるようなもののみからなる数列を \(D^{(1)}\)とします。

2-1. \(d = -1\) のとき

\(f_d(C,D,x) = \min(|C|,|D|)\) です（これが再帰の base case となります）。

2-2. \(d \geq 0\) で、\(x\) の \(2^d\) の位が \(0\) のとき

対称性より\(|C^{(0)}| \leq |D^{(1)}|\) の場合について考えれば十分です。 \(C^{(0)}\) の要素と \(D^{(1)}\) の要素の xor および \(C^{(1)}\) の要素と \(D^{(0)}\) の要素の xor は必ず \(2^d\) 以上となり、\(2^d > x\) より \(x\) 以上にもなります。

2-2-1. \(|C^{(1)}| \leq |D^{(0)}|\) のとき

\(g_d(C,D,x) = |C^{(0)}| + |C^{(1)}|\) です（上下から簡単に評価できます）。

2-2-2. \(|C^{(1)}| > |D^{(0)}|\) のとき

\(g_d(C,D,x) = |C^{(0)}| + |D^{(0)}| + \min(|C^{(1)}| - |D^{(0)}|, |D^{(1)}| - |C^{(0)}|, g_{d-1}(C^{(1)}, D^{(1)}, x))\) です（\(C^{(0)}\) の要素と \(D^{(1)}\) の要素からなるペアおよび \(D^{(0)}\) の要素と \(C^{(1)}\) の要素からなるペアを貪欲に作ってよく、ここから従います）。

2-3. \(d \geq 0\) で、\(x\) の \(2^d\) の位が \(1\) のとき

\(C^{(0)}\) の要素と \(D^{(0)}\) の要素の xor および \(C^{(1)}\) の要素と \(D^{(1)}\) の要素の xor は必ず \(2^d\) 未満となり、\(2^d \leq x\) より \(x\) 未満にもなります。したがって、\(g_d(C,D,x) = g_{d-1}(C^{(0)}, D^{(1)}, x) + g_{d-1}(C^{(1)}, D^{(0)}, x)\) です。

以上よりこの再帰にしたがって計算することで求めたい値が得られました。各 \(d\) に対して \(O(N)\) 個の点で評価しているため全体として判定問題は \(O(N \log \max A_i)\) で解け、全体としてこの問題を時間計算量 \(O(N (\log \max A_i) ^ 2)\) で解くことができました。再帰の計算式を観察することで実は \(f(A,x) = \lfloor \frac {g(A,A,x)}{2} \rfloor\) が成り立つこともわかるので、\(f\) や \(f_d\) を使わずに答えを得ることも可能です。

以下は実装例ですが、解説と変数名が違う部分があること、再帰で評価する際に数列を陽を持たずに \(A\) を sort して \(A[l:r]\) の形で保持していることに注意してください。また、\(C = A[l:r]\) は\(|C^{(0)}| = A[l:m]\)、\(|C^{(1)}| = A[m:r]\) というように分割できますが、この \(m\) を求めるために尺取り法の要領で前計算をしています（実際は、再帰の中で毎回二分探索をすることにより \(m\) を求める解法でも AC できることを確認済みです）。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 200010;
vector<vector<int>> v(30, vector<int>(N));

int g(vector<int> &a, int xl, int xr, int yl, int yr, int x, int d) {
	if (xl == xr || yl == yr) return 0;
	if (d == -1) return min(xr - xl, yr - yl);
	int xm = v[d][xl], ym = v[d][yl];
	int x1 = xm - xl, x2 = xr - xm, y1 = ym - yl, y2 = yr - ym;
	if (x >> d & 1) {
		int c1 = g(a, xl, xm, ym, yr, x, d - 1);
		int c2 = g(a, xm, xr, yl, ym, x, d - 1);
		return c1 + c2;
	}
	else {
		bool f1 = x1 <= y2;
		bool f2 = x2 <= y1;
		if (f1 && f2) return x1 + x2;
		else if (!f1 && !f2) return y1 + y2;
		else if (f1 && !f2) {
			int r = min({ g(a, xm, xr, ym, yr, x, d - 1), y2 - x1, x2 - y1 });
			return r + x1 + y1;
		}
		else if (!f1 && f2) {
			int r = min({ g(a, xl, xm, yl, ym, x, d - 1), x1 - y2, y1 - x2 });
			return r + x2 + y2;
		}
	}
}

int f(vector<int> &a, int l, int r, int x, int d) {
	if (l == r) return 0;
	if (d == -1) return (r - l) / 2;
	int m = v[d][l];
	int x1 = m - l, x2 = r - m;
	if (x >> d & 1) return g(a, l, m, m, r, x, d - 1);
	else {
		if (x1 <= x2) return min((x2 - x1) / 2, f(a, m, r, x, d - 1)) + x1;
		else return min((x1 - x2) / 2, f(a, l, m, x, d - 1)) + x2;
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> a(2 * n);
	for (int i = 0; i < 2 * n; i++) cin >> a[i];
	sort(a.begin(), a.end());
	a.push_back(7 << 28);
	int ans = 0;
	for (int i = 0; i < 30; i++) {
		int f = 0;
		int z = 1 << (i + 1);
		int nxt = a[0] / z * z + z / 2;
		int mx = a[0] / z * z + z;
		int tmp = -1;
		for (int j = 0; j < 2 * n + 1; j++) {
			if (a[j] >= nxt && tmp == -1) tmp = j;
			if (a[j] >= mx) {
				for (int k = f; k < j; k++) v[i][k] = tmp;
				f = j;
				nxt = a[j] / z * z + z / 2;
				mx = a[j] / z * z + z / 2;
				tmp = -1;
			}
			if (a[j] >= nxt && tmp == -1) tmp = j;
		}
	}
	for (int b = 29; b >= 0; b--) {
		int tmp = ans | (1 << b);
		int cnt = f(a, 0, 2 * n, tmp, 29);
		if (cnt >= (n + 1) / 2) ans |= 1 << b;
	}
	cout << ans << '\n';
}