Xét thao tác đổi chỗ $2$ số $a_i$ và $b_i$, ta thấy $f(a)$ sẽ trở thành $f(a)\oplus a_i\oplus b_i$, còn $f(b)$ trở thành $f(b)\oplus a_i\oplus b_i$. Nói cách khác, $f(a)$ và $f(b)$ sẽ được $\text{xor}$ với cùng một số.

Xét $f(a)$ và $f(b)$ theo thứ tự bit giảm dần, ta thấy, nếu bit thứ $i$ của $f(a)$ và $f(b)$ khác nhau, thì sau khi thực hiện các thao tác đổi chỗ, hai bit này vẫn sẽ khác nhau.

Ngược lại, nếu bit thứ $i$ của $f(a)$ và $f(b)$ giống nhau, để $f(a)+f(b)$ đạt giá trị nhỏ nhất, ta sẽ muốn bit thứ $i$ của $f(a)$ và $f(b)$ cùng bằng $0$. Ta sẽ kiểm tra điều kiện này bằng khử Gauss.

Code mẫu:

Code mẫu

Copy

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 1;

bool gauss(vector<bitset<N>> a, int m) {
  int k = a.size();
  for (int c = 0, r = 0; c < m && r < k; ++c) {
    for (int i = r; i < k; ++i) {
      if (a[i][c]) {
        swap(a[r], a[i]);
        break;
      }
    }
    if (!a[r][c]) {
      continue;
    }
    for (int i = 0; i < k; ++i) {
      if (i != r && a[i][c]) {
        a[i] ^= a[r];
      }
    }
    ++r;
  }

  for (int i = 0; i < k; ++i) {
    if (a[i][m]) {
      a[i][m] = 0;
      if (a[i].none()) {
        return 0;
      }
    }
  }

  return 1;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  long long xa = 0, xb = 0;
  vector<long long> a(n), b(n);
  for (long long &v : a) {
    cin >> v;
    xa ^= v;
  }
  for (long long &v : b) {
    cin >> v;
    xb ^= v;
  }
  for (int i = 0; i < n; ++i) {
    a[i] ^= b[i];
  }

  long long ans = 0;
  vector<bitset<N>> t;
  for (int i = 61; i >= 0; --i) {
    int fa = (xa >> i) & 1, fb = (xb >> i) & 1;
    if (fa != fb) {
      ans += 1ll << i;
      continue;
    }
    bitset<N> bs;
    for (int j = 0; j < n; ++j) {
      bs[j] = (a[j] >> i) & 1;
    }
    bs[n] = fa;
    t.push_back(bs);
    if (!gauss(t, n)) {
      ans += 1ll << (i + 1);
      t.back()[n].flip();
    }
  }

  cout << ans;
}