OrAndSum [SRM724 Div1 Easy]

pairOr[i] = x[i] or x[i + 1]
pairSum[i] = x[i] + x[i + 1]
であるpairOrとpairSumが与えられる。
与えられる2つの配列を満たすように配列xを構築できるか判定せよ。

解法

まず、x[i]とx[i+1]のそれぞれで使えるビットはpairOr[i]で1が立っている部分だけである。
次に、d=pairSum[i] - pairOr[i]を考えてみる。
和-orはandになるというのがあり、これよりpairAnd[i]も作れることになる。
　
あとは、pairOrとpairAndを見ながら構築していけばいい。
まず、pairAnd[i]==1であるやつを1で埋める。
次に、埋まっている所から幅優先でpairOr[i]に矛盾しないように埋めていく。
全て埋まるまで回して埋まれば答え。
　
下の解法では一応最後にチェックをしている。

typedef long long ll;
#define no "Impossible"
#define yes "Possible"
#define MMSK 61
struct OrAndSum {
    string isPossible(vector<long long> pairOr, vector<long long> pairSum) {
        int n = pairOr.size();
        vector<vector<int>> table(n + 1, vector<int>(64, -1));
        vector<vector<int>> type(n, vector<int>(64, -1));

        rep(i, 0, n) {
            ll d = pairSum[i] - pairOr[i];
            if (d < 0) return no;

            rep(m, 0, MMSK) {
                if (pairOr[i] & (1LL << m)) type[i][m] = 0;
                else {
                    if (table[i][m] == 1) return no;
                    if (table[i + 1][m] == 1) return no;
                    table[i][m] = table[i + 1][m] = 0;
                }
            }
            rep(m, 0, MMSK) if (d & (1LL << m) and type[i][m] == 0) {
                type[i][m] = 1;
                if (table[i][m] == 0) return no;
                if (table[i + 1][m] == 0) return no;
                table[i][m] = table[i + 1][m] = 1;
            }
        }

        while (1) {
            queue<pair<int, int>> que;
            rep(i, 0, n) rep(m, 0, MMSK) if (type[i][m] == 0) {
                if (table[i][m] < 0 and table[i + 1][m] < 0) continue;
                if (table[i][m] < 0) que.push({ i, m });
                if (table[i + 1][m] < 0) que.push({ i, m });
            }

            while (!que.empty()) {
                int i, m; tie(i, m) = que.front(); que.pop();
                if (table[i][m] < 0) {
                    table[i][m] = 1 - table[i + 1][m];
                    if (i) que.push({ i - 1, m });
                }
                if (table[i + 1][m] < 0) {
                    table[i + 1][m] = 1 - table[i][m];
                    if (i + 1 < n) que.push({ i + 1, m });
                }
            }

            int ok = 1;
            rep(i, 0, n + 1) rep(m, 0, MMSK) if (table[i][m] < 0 and ok) {
                ok = 0;
                table[i][m] = 0;
            }
            if (ok) break;
        }

        //rep(i, 0, n + 1) { rep(m, 0, MMSK) printf("%d\t", table[i][m]); printf("\n"); }

        vector<ll> x(n + 1);
        x[0] = 0;
        rep(m, 0, MMSK) if (table[0][m]) x[0] += 1LL << m;
        rep(i, 0, n) {
            x[i + 1] = pairSum[i] - x[i];
            if (x[i + 1] < 0) return no;
            if ((x[i] | x[i + 1]) != pairOr[i]) return no;
        }
        return yes;
    }
};