ABC 347

D - Popcount and XOR

考察

自力で解けたが1日考えた。

$c = \mathrm{popcount}(C)$ とする。$a

$X \oplus Y = C$ のことは一旦忘れ $\mathrm{popcount}(X) = a, \mathrm{popcount}(Y) = b$ だけを考える。 $X$, $Y$ で極力同じ場所の bit を立てた場合 $\mathrm{popcount}(X \oplus Y) = |a-b|$。 $X$, $Y$ で同じ場所に bit を建てなかった場合 $\mathrm{popcount}(X \oplus Y) = a+b$ であるから $X \oplus Y = C$ になる必要条件は

である。また同じ場所に立っていた bit を別の場所で立てた場合 popcount の値は2ずつ変わるので $a+b$ と $c$ の parity は同じにならなければならない。

たとえば、下記のように $X$ の 2 bit 目の bit を下げて 4 bit 目を上げると xor を取ると popcount の値が2増える。逆に $X,Y$ のどちらかだけに立っていた bit の位置を1つの場所に移動させると popcount の値が 2 減る。 \begin{align} X = 00111 \Rightarrow X^\prime &= 10011 \nonumber \\ Y &= 01111 \nonumber \end{align}

$X, Y$ で何 bit 同じ場所に bit が立っているかを考える。考えうる popcount の最大値 $a+b$ から最終的に残したい $c$ 個を引いて、残りの bit で pair を作れば良いから $X, Y$ の $\frac{a+b-c}{2}$ 箇所 で同じところの bit が立っている。 これより $X$ の立っている bit のうち $a - \frac{a+b-c}{2}$ 箇所は $Y$ では立っていない。

解法

$X = 0$ で初期化する。 $C$ のうち bit が立っている $a - \frac{a+b-c}{2}$ 箇所を自由に選んで同じ箇所を $X$ でも立てる。 $C$ のうち bit が立っていない $\frac{a+b-c}{2}$ 箇所を自由に選んで同じ箇所を $X$ では bit を立てる。 条件に合うような bit の立て方ができなかったとき -1 を出力。

無事に bit を立て終わったら $Y = X \oplus C$ とする。

void solve() {
    ll a, b, C;
    cin >> a >> b >> C;

    ll c = __builtin_popcountll(C);
    if (c < abs(a - b) || a + b < c || (a + b) % 2 != c % 2) {
        cout << -1 << endl;
        return;
    }

    ll x = 0;
    ll overrap = (a + b - c) / 2;
    a -= overrap;
    rep(i, 60) {
        if (a && (C & (1LL << i))) {
            x ^= 1LL << i;
            a--;
        }
    }
    rep(i, 60) {
        if (overrap && !(C & (1LL << i))) {
            x ^= 1LL << i;
            overrap--;
        }
    }
    if (a || overrap) {  // これがないと 60 60 3 という入力例で WA になる
        cout << -1 << endl;
        return;
    }

    ll y = x ^ C;
    cout << x << ' ' << y << endl;
}