TopXorer [SRM723 Div1 Easy]

N個の配列Aがある。
ここから、0≦B[i]≦A[i]を満たすようにN個の配列Bを作る。
B[0] xor B[1] xor ... xor B[N-1]の最大値は？

解法

上のビットから答えを確定していく。
配列A[i]を昇順ソートした時にdビット目が立っているものが2つ以上あれば、1つ目でdビットを1にして、2つめで1～(d-1)ビットを1にできるため、最大化できる。
そういう場面となったら、最大値として答えを出す。
　
dビット目が立っているものが1つだけなら、そのビットはその数を使って1に確定させる。
dビット以下はまだ自由に変えられるため、1＜＜dを引いて置いておく。
　
この動作を貪欲にやっていく。

struct TopXorer {
    int maximalRating(vector <int> x) {
        int ans = 0;

        rrep(d, 31, 0) {
            sort(x.begin(), x.end(), greater<int>());
            assert(0 < x.size());

            if (x.size() == 1) {
                ans += x[0];
                return ans;
            }

            if (!(x[0] & (1 << d))) {
                continue;
            }

            if (x[1] & (1 << d)) {
                ans += (1 << (d + 1)) - 1;
                return ans;
            }

            ans += 1 << d;
            x.push_back(x[0] - (1 << d));
            x.erase(x.begin(), x.begin() + 1);
        }

        return ans;
    }
};