競技プログラミング日記

主に AtCoder の記事です

AtCoder Regular Contest 124B

 

ARC124B

2つのvector に対して,次は同値.

  • ある並べ替えで一致
  • multiset として一致
  • ソートしたvectors が一致


よって, \(x\) を固定したとき, \([a_{i} \oplus x ]_{i \in N}, \ b\) が multiset として一致していれば良い.
\(x\) の候補は \(a_{0} \oplus b{j} \ (j \in N)\) のみ.

使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {
  ll n;
  cin >> n;
  vll a(n); rep(i,n) { cin >> a[i]; }
  vll b(n); rep(i,n) { cin >> b[i]; }

  multiset<ll> msb;
  rep(i,n) msb.insert(b[i]);

  set<ll> sx;
  rep(i,n){
    sx.insert(a[0] ^ b[i]);
  }

  vll ans;
  for(ll x: sx){
    multiset<ll> ms;
    rep(i,n){
      ms.insert(x ^ a[i]);
    }

    if(ms == msb){
      ans.push_back(x);
    }
  }

  cout << ans.size() << endl;
  rep(i,ans.size()){
    cout << ans[i] << endl;
  }

  return 0;
}