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

• 問題: No.3736 Purely Bool Hell
• ユーザー: 👑 kencho
• 提出日時: 2026-09-08 00:04:02
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 88 ms / 3,000 ms
• コード長: 9,532 bytes
• コンパイル時間: 2,791 ms
• コンパイル使用メモリ: 347,836 KB
• 実行使用メモリ: 6,528 KB
• 最終ジャッジ日時: 2026-09-19 13:14:56
• 合計ジャッジ時間: 9,700 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge3_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);

    // 中央反対角線以外には、指定 XOR を満たす最大数の 1 を置く。
    vector<int> columns;
    columns.reserve(n);
    for (int d = 0; d < diagonalCount; ++d) {
        if (d == center) {
            continue;
        }

        columns.clear();
        int left = max(0, d - n + 1);
        int right = min(n - 1, d);
        for (int c = left; c <= right; ++c) {
            if (active[c]) {
                columns.push_back(c);
            }
        }

        if ((columns.size() & 1) != static_cast<size_t>(target[d])) {
            if (columns.empty()) {
                return false;
            }
            columns.pop_back();
        }

        for (int c : columns) {
            matrix[(d - c) * n + c] = 1;
            covered[c] = 1;
        }
    }

    /*
    未被覆の 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;
}