ABC171 E - Red Scarf (500)
bit毎に考える
$ A_iと$ A_jでそのbitの値が違う場合、$ B_iと$ B_jでもそのbitの値は異なる
求める配列を$ Bとする
bit毎に見たときに
1の登場回数が偶数の場合、$ A_iが1の所は$ B_iでも1、逆も同じく
自分が1の時、残りは1のが奇数個、0のが偶数個登場するので1のところが1にならないと矛盾する
1の登場回数が奇数の場合、$ A_iが1の所は$ B_iは0、逆も同じく
全体で$ O(N \log \max A)
Nが奇数の場合、
bit毎に1の登場回数が奇数のものがある場合は解無し
自分が1の時、残りは1のが偶数個、0のも偶数個登場するのでどう割り当ててもXORが1にならない
そうでない場合は$ B_i = A_iで作れる
解説の解法
$ S = A_0 \oplus A_1 \oplus ... \oplus A_{n-1}とする
$ Sには$ B_iがそれぞれN-1回含まれてているので$ S = B_0 \oplus B_1 \oplus ... \oplus B_{n-1}
よって$ B_i = S \oplus A_i