#1171301 (C++23(gcc16)) No.3736 Purely Bool Hell

• 問題: No.3736 Purely Bool Hell
• ユーザー: 👑 kencho
• 提出日時: 2026-07-13 02:44:48
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 87 ms / 3,000 ms
• コード長: 10,965 bytes
• コンパイル時間: 2,655 ms
• コンパイル使用メモリ: 363,904 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-19 12:35:08
• 合計ジャッジ時間: 8,496 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 39

ソースコード

#include <bits/stdc++.h>
using namespace std;

vector<int> smallAnswer[4];

/*
N <= 3 について、全 0/1 行列を列挙する。

key =
    row_and_mask
  | (column_or_mask << N)
  | (diagonal_xor_mask << (2 * N))
*/
void initializeSmallCases() {
    for (int n = 1; n <= 3; ++n) {
        smallAnswer[n].assign(1 << (4 * n - 1), -1);

        for (int matrixMask = 0;
             matrixMask < (1 << (n * n));
             ++matrixMask) {

            int xMask = 0;
            int yMask = 0;
            int zMask = 0;

            for (int i = 0; i < n; ++i) {
                int value = 1;
                for (int j = 0; j < n; ++j) {
                    value &= (matrixMask >> (i * n + j)) & 1;
                }
                xMask |= value << i;
            }

            for (int j = 0; j < n; ++j) {
                int value = 0;
                for (int i = 0; i < n; ++i) {
                    value |= (matrixMask >> (i * n + j)) & 1;
                }
                yMask |= value << j;
            }

            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    if ((matrixMask >> (i * n + j)) & 1) {
                        zMask ^= 1 << (i + j);
                    }
                }
            }

            int key =
                xMask
                | (yMask << n)
                | (zMask << (2 * n));

            smallAnswer[n][key] = matrixMask;
        }
    }
}

/*
active[c] = 0:
    列 c はすべて 0

active[c] = 1:
    列 c には少なくとも 1 個の 1 が必要

さらに、反対角線 d の XOR を target[d] にする。
*/
bool buildColumns(
    int n,
    const vector<char>& active,
    const vector<char>& target,
    vector<char>& matrix
) {
    const int diagonalCount = 2 * n - 1;
    const int center = n - 1;

    fill(matrix.begin(), matrix.end(), 0);

    vector<char> covered(n, 0);

    int activeCount = 0;
    for (int c = 0; c < n; ++c) {
        activeCount += active[c];
    }

    /*
    中央以外の反対角線。

    target[d] = 1 なら、active なマスに 1 を 1 個置く。
    target[d] = 0 なら何も置かない。
    */
    for (int d = 0; d < diagonalCount; ++d) {
        if (d == center || target[d] == 0) {
            continue;
        }

        int left = max(0, d - n + 1);
        int right = min(n - 1, d);

        int chosenColumn = left;
        while (chosenColumn <= right && !active[chosenColumn]) {
            ++chosenColumn;
        }

        if (chosenColumn > right) {
            return false;
        }

        int row = d - chosenColumn;
        matrix[row * n + chosenColumn] = 1;
        covered[chosenColumn] = 1;
    }

    bool hasCoveredColumn = false;
    for (int c = 0; c < n; ++c) {
        if (active[c] && covered[c]) {
            hasCoveredColumn = true;
        }
    }

    /*
    中央の parity を変更する自由度がなく、
    全 active 列を中央で埋めた parity も合わない場合。

    target[d] = 0 の非中央反対角線に 1 を 2 個置き、
    XOR を変えずに被覆済み列を作る。
    */
    if (!hasCoveredColumn
        && ((activeCount & 1) != target[center])) {

        bool found = false;

        for (int d = 0; d < diagonalCount && !found; ++d) {
            if (d == center || target[d] != 0) {
                continue;
            }

            int left = max(0, d - n + 1);
            int right = min(n - 1, d);

            int c1 = -1;
            int c2 = -1;

            for (int c = left; c <= right; ++c) {
                if (!active[c]) {
                    continue;
                }

                if (c1 == -1) {
                    c1 = c;
                } else {
                    c2 = c;
                    break;
                }
            }

            if (c2 != -1) {
                matrix[(d - c1) * n + c1] = 1;
                matrix[(d - c2) * n + c2] = 1;

                covered[c1] = 1;
                covered[c2] = 1;

                found = true;
            }
        }

        if (!found) {
            return false;
        }
    }

    /*
    未被覆の active 列を中央反対角線で被覆する。
    */
    int centerParity = 0;
    int optionalColumn = -1;

    for (int c = 0; c < n; ++c) {
        if (!active[c]) {
            continue;
        }

        if (covered[c]) {
            // この列は既に被覆されているため、中央の値は自由。
            optionalColumn = c;
        } else {
            matrix[(center - c) * n + c] = 1;
            centerParity ^= 1;
        }
    }

    if (centerParity != target[center]) {
        if (optionalColumn == -1) {
            return false;
        }

        matrix[(center - optionalColumn) * n + optionalColumn] = 1;
    }

    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    initializeSmallCases();

    int T;
    cin >> T;

    while (T--) {
        int N;
        cin >> N;

        vector<int> X(N);
        vector<int> Y(N);
        vector<int> Z(2 * N - 1);

        for (int& value : X) cin >> value;
        for (int& value : Y) cin >> value;
        for (int& value : Z) cin >> value;

        vector<int> answer(N * N, 0);
        bool possible = true;

        /*
        N <= 3 は全列挙表から各ビットの行列を取得する。
        */
        if (N <= 3) {
            for (int bit = 0; bit < 30 && possible; ++bit) {
                int xMask = 0;
                int yMask = 0;
                int zMask = 0;

                for (int i = 0; i < N; ++i) {
                    xMask |= ((X[i] >> bit) & 1) << i;
                    yMask |= ((Y[i] >> bit) & 1) << i;
                }

                for (int d = 0; d < 2 * N - 1; ++d) {
                    zMask |= ((Z[d] >> bit) & 1) << d;
                }

                int key =
                    xMask
                    | (yMask << N)
                    | (zMask << (2 * N));

                int matrixMask = smallAnswer[N][key];

                if (matrixMask == -1) {
                    possible = false;
                    break;
                }

                for (int position = 0;
                     position < N * N;
                     ++position) {

                    if ((matrixMask >> position) & 1) {
                        answer[position] |= 1 << bit;
                    }
                }
            }
        } else {
            const int diagonalCount = 2 * N - 1;

            vector<char> active(N);
            vector<char> target(diagonalCount);
            vector<char> matrix(N * N);

            for (int bit = 0; bit < 30 && possible; ++bit) {
                bool hasXOne = false;
                bool hasYZero = false;

                for (int i = 0; i < N; ++i) {
                    hasXOne |= ((X[i] >> bit) & 1) != 0;
                    hasYZero |= ((Y[i] >> bit) & 1) == 0;
                }

                /*
                行全体を 1 にする要求と、
                列全体を 0 にする要求が交差する。
                */
                if (hasXOne && hasYZero) {
                    possible = false;
                    break;
                }

                const int bitValue = 1 << bit;

                if (hasYZero) {
                    /*
                    全 X bit は 0。

                    Y bit=0 の列が各行に必要な 0 を与えるため、
                    Y bit=1 の列を被覆すればよい。
                    */
                    for (int j = 0; j < N; ++j) {
                        active[j] = (Y[j] >> bit) & 1;
                    }

                    for (int d = 0; d < diagonalCount; ++d) {
                        target[d] = (Z[d] >> bit) & 1;
                    }

                    if (!buildColumns(N, active, target, matrix)) {
                        possible = false;
                        break;
                    }

                    for (int position = 0;
                         position < N * N;
                         ++position) {

                        if (matrix[position]) {
                            answer[position] |= bitValue;
                        }
                    }
                } else if (hasXOne) {
                    /*
                    全 Y bit は 1。

                    B=1-A を転置して、列版の部分問題にする。
                    */
                    for (int i = 0; i < N; ++i) {
                        active[i] = ((X[i] >> bit) & 1) == 0;
                    }

                    for (int d = 0; d < diagonalCount; ++d) {
                        int length =
                            (d < N ? d + 1 : 2 * N - 1 - d);

                        target[d] =
                            ((Z[d] >> bit) & 1)
                            ^ (length & 1);
                    }

                    if (!buildColumns(N, active, target, matrix)) {
                        possible = false;
                        break;
                    }

                    /*
                    matrix[j][i] = B[i][j]
                    A[i][j] = 1-B[i][j]
                    */
                    for (int i = 0; i < N; ++i) {
                        for (int j = 0; j < N; ++j) {
                            if (matrix[j * N + i] == 0) {
                                answer[i * N + j] |= bitValue;
                            }
                        }
                    }
                } else {
                    /*
                    全 X bit=0、全 Y bit=1。

                    P_i=(i,(i+2) mod N) を 1 にし、
                    各反対角線の代表マスで XOR を調整する。
                    */
                    fill(target.begin(), target.end(), 0);

                    // P_i を配置し、その反対角線 parity を記録する。
                    for (int i = 0; i < N; ++i) {
                        int j = (i + 2) % N;

                        answer[i * N + j] |= bitValue;
                        target[i + j] ^= 1;
                    }

                    // R_d=(floor(d/2),ceil(d/2))
                    for (int d = 0; d < diagonalCount; ++d) {
                        int i = d / 2;
                        int j = d - i;

                        int value =
                            ((Z[d] >> bit) & 1)
                            ^ target[d];

                        if (value) {
                            answer[i * N + j] |= bitValue;
                        }
                    }
                }
            }
        }

        if (!possible) {
            cout << -1 << '\n';
            continue;
        }

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (j > 0) cout << ' ';
                cout << answer[i * N + j];
            }
            cout << '\n';
        }
    }

    return 0;
}