東京工業大学プログラミングコンテスト2019：C - XOR Filling

問題

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_c

解法

-1 でない a_i の xor を t，-1 である a_i の個数を cnt とすると，0 以上 X 以下の数 cnt 個の xor が X^t となればよい．これは X^t が X * 2 以上であるときは構成できない．そうでないときは，目的の xor が X より大きいときは X，そうでないときはその xor で -1 を置き換えていけばよい．O(N)．

解答

https://atcoder.jp/contests/ttpc2019/submissions/7217714