まず、数列が一つだけの場合を考えてみます。つまり、次のような問題を考えます。

長さ \(N\) の数列 \(A\) が与えられる。集合 \(U=\{x|x\in\mathbb{N},1\leq x\leq N\}\) の空でない任意の部分集合 \(S\) をとったとき、\(S=\{k_1,k_2,\cdots k_l\}\) として、\((A_{k_1} xor A_{k_2} xor \cdots xor A_{k_l})\) の最大値を求めよ。

この問題は、数の \(2\) 進数表現を行列に並べ、掃き出し法を行って基底の数を減らすことで、\(A\) のどの値よりも大きい最小の \(2\) べきを \(X\) として、\(O((N+X)\log X)\) で解くことができます。

さて、本題に戻りましょう。 この問題では \(2\) つの数列で同じことをしなければなりませんが、解法はほとんど同じです。 \(2\) つの数列の \(xor\) がそれぞれ独立となるように、数列 \(C_i = 2^{10}A_i+B_i\) を考えて、\(C_i\) の \(xor\) でできる数をすべて列挙してやれば、\(C\) の \(xor\) の値から \(A,B\) での値を復元することができ、この問題を解くことができました。

計算量は、\(C\) のどの値よりも大きい最小の \(2\) べきを \(Y\) とすれば、掃き出し法に \(O(N\log Y)\), その後の \(C\) の全列挙に \(O(Y\log Y)\) かかり、\(O((N+Y)\log Y)\) となります。 この問題の制約下では、\(Y\) は高々 \(2^{20}\) なので、この解法で十分間に合います。

#include <iostream>
#define rep(i, n) for(int i = 0; i < int(n); i++)
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return true;
	}
	return false;
}
int N, A[500010], B[500010], C[500010];
int main() {
	std::cin >> N;
	rep(i, N) std::cin >> A[i];
	rep(i, N) std::cin >> B[i];
	rep(i, N) C[i] = (A[i] << 10) + B[i];
	int now = 0;
	for (int i = 19; i >= 0; i--) {
		for (int j = now + 1; j < N; j++) {
			if (C[j] & (1 << i)) {
				std::swap(C[now], C[j]);
				break;
			}
		}
		if (!(C[now] & (1 << i))) continue;
		rep(j, N) {
			if (j != now && (C[j] & (1 << i))) C[j] ^= C[now];
		}
		now++;
	}
	int ans = 0;
	rep(i, 1 << now) {
		int x = 0;
		rep(j, now) {
			if (i & (1 << j)) x ^= C[j];
		}
		chmax(ans, x / (1 << 10) + x % (1 << 10));
	}
	std::cout << ans << std::endl;
	return 0;
}