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

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

解説

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

自明な場合分けとして、欠損したものがなければ、XORをとって、Xと一致するかを見ればいい。

0≦ai≦Xであるという条件がなければ、欠損したaiがあれば必ず構築可能である。
欠損したaiが1つであれば、全体をXORしてXになるためにはai = X xor (ai以外のxor和)である必要がある。
このaiが0≦ai≦XであればOK、そうでないなら-1

欠損したaiが2つ以上あれば、使うのは2つで良さそう。
「X xor 欠損していないaiのxor和」を作ろうとした時に最上位ビットだけ立っているものと、最上位ビット以外が立っているもので作れる。
2つ以外は0で埋めておけばいい。
最上位ビットだけ立っているものがすでにXを超えている可能性があるので、それをチェックしておく。
どちらもX以下ならOK, そうでないなら-1

int N, X, A[501010];
//---------------------------------------------------------------------------------------------------
bool solve() {
    int xo = X;
    int cnt = 0;
    rep(i, 0, N) {
        if (A[i] < 0) cnt++;
        else xo ^= A[i];
    }

    if (cnt == 0) {
        if (xo == 0) return true;
        else return false;
    } else if (cnt == 1) {
        if (0 <= xo and xo <= X) {
            rep(i, 0, N) if(A[i] < 0) A[i] = xo;
            return true;
        }
        else return false;
    } else {
        int ans1 = 1;
        while(ans1 < xo) ans1 *= 2;
        ans1 /= 2;
        int ans2 = xo - ans1;

        int flag = 0;
        rep(i, 0, N) if(A[i] < 0) {
            if(flag == 0) A[i] = ans1, flag++;
            else if(flag == 1) A[i] = ans2, flag++;
            else A[i] = 0;
        }

        if (ans1 <= X and ans2 <= X) return true;
        else return false;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X;
    rep(i, 0, N) cin >> A[i];

    auto ans = solve();

    if (ans) {
        rep(i, 0, N) {
            if(i) printf(" ");
            printf("%d", A[i]);
        }
        printf("\n");
    } else {
        printf("-1\n");
    }
}