# ARC124-B XOR Matching 2

788diff
https://atcoder.jp/contests/arc124/tasks/arc124_b

## 解法

よい数としてありえる候補は$\{ A_1\oplus B_{i} | 1\le i\le N\}$のたかだか$N$個である。この候補に対してそれらが良い数か判定できれば良い。

判定したい値を$x$とする。$A_{i}\oplus B_{j} = x$であることと$A_{i}\oplus x = B_{j}$であることは同値である。よって$\{ A_{i}\oplus x | 1\le i\le N\}$が多重集合として$B$と一致しているとき、またそのときに限り$x$は良い数である。

## 実装

#include <bits/stdc++.h>

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int N;
    std::cin >> N;
    std::vector<int> A(N), B(N);
    for (auto& a : A) std::cin >> a;
    for (auto& a : B) std::cin >> a;
    std::sort(B.begin(), B.end());
    std::vector<int> ans;
    ans.reserve(N);
    for (int i{} ; i < N ; i++) {
        int x{A[0] ^ B[i]};
        std::vector<int> C(N);
        for (int j{} ; j < N ; j++) {
            C[j] = A[j] ^ x;
        }
        std::sort(C.begin(), C.end());
        if (B == C) ans.push_back(x);
    }
    std::sort(ans.begin(), ans.end());
    ans.erase(std::unique(ans.begin(), ans.end()), ans.end());
    std::cout << ans.size() << '\n';
    for (auto a : ans) std::cout << a << '\n';
}

[提出](https://atcoder.jp/contests/arc124/submissions/58495485)

## 感想

候補の数がたかだか$N$個なの中々気づけなかった。アハ体験。

重複を取り除き忘れて1ミス。詰めが甘い...