#1172706 (C++23(gcc16)) No.3739 Stronger Network

• 問題: No.3739 Stronger Network
• ユーザー: 👑 kencho
• 提出日時: 2026-07-24 06:08:14
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 34 ms / 2,000 ms
• コード長: 3,861 bytes
• コンパイル時間: 3,291 ms
• コンパイル使用メモリ: 367,248 KB
• 実行使用メモリ: 6,640 KB
• 最終ジャッジ日時: 2026-09-19 12:36:43
• 合計ジャッジ時間: 7,928 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge1_0

ファイルパターン	結果
sample	AC * 2
other	AC * 48

ソースコード

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

vector<int> cyclic_gray(int n) {
    if (n == 2) return {0, 1};
    int p = 1;
    while ((p << 1) <= n) p <<= 1;
    if (p == n) {
        vector<int> result(n);
        for (int i = 0; i < n; ++i) result[i] = i ^ (i >> 1);
        return result;
    }

    int r = n - p;
    vector<int> small = cyclic_gray(r);
    int u = small[0], v = small[1];
    int changed_bit = __builtin_ctz(u ^ v);

    vector<int> base(p);
    for (int i = 0; i < p; ++i) {
        int x = i ^ (i >> 1);
        int bit0 = x & 1;
        int bitb = (x >> changed_bit) & 1;
        if (bit0 != bitb) x ^= 1 | (1 << changed_bit);
        base[i] = x ^ u;
    }

    vector<int> result;
    result.reserve(n);
    result.push_back(u);
    result.push_back(p + u);
    for (int i = r - 1; i >= 1; --i) result.push_back(p + small[i]);
    result.push_back(v);
    for (int i = 2; i < p; ++i) result.push_back(base[i]);
    return result;
}

int bit_length(int x) {
    int result = 0;
    while ((1 << result) < x) ++result;
    return result;
}

pair<vector<int>, vector<int>> optimal_bit_positions(int h, int w) {
    int rh = bit_length(h), rw = bit_length(w);
    vector<int> bh(rh), bw(rw);
    for (int i = 0; i < rh; ++i) bh[i] = ((h - 1) >> (rh - 1 - i)) & 1;
    for (int j = 0; j < rw; ++j) bw[j] = ((w - 1) >> (rw - 1 - j)) & 1;

    const unsigned long long INF = numeric_limits<unsigned long long>::max();
    vector<vector<unsigned long long>> dp(rh + 1, vector<unsigned long long>(rw + 1, INF));
    vector<vector<unsigned char>> take_h(rh + 1, vector<unsigned char>(rw + 1, 0));
    dp[rh][rw] = 0;
    for (int i = rh; i >= 0; --i) {
        for (int j = rw; j >= 0; --j) {
            if (i == rh && j == rw) continue;
            int remaining = (rh - i) + (rw - j);
            if (i < rh) {
                unsigned long long candidate =
                        (static_cast<unsigned long long>(bh[i]) << (remaining - 1))
                        + dp[i + 1][j];
                if (candidate < dp[i][j]) {
                    dp[i][j] = candidate;
                    take_h[i][j] = 1;
                }
            }
            if (j < rw) {
                unsigned long long candidate =
                        (static_cast<unsigned long long>(bw[j]) << (remaining - 1))
                        + dp[i][j + 1];
                if (candidate < dp[i][j]) {
                    dp[i][j] = candidate;
                    take_h[i][j] = 0;
                }
            }
        }
    }

    vector<int> pos_h(rh), pos_w(rw);
    int i = 0, j = 0;
    for (int output_bit = rh + rw - 1; output_bit >= 0; --output_bit) {
        if (i < rh && (j == rw || take_h[i][j])) {
            pos_h[rh - 1 - i] = output_bit;
            ++i;
        } else {
            pos_w[rw - 1 - j] = output_bit;
            ++j;
        }
    }
    return {pos_h, pos_w};
}

unsigned long long deposit_bits(int x, const vector<int>& positions) {
    unsigned long long result = 0;
    for (int bit = 0; bit < (int)positions.size(); ++bit) {
        if ((x >> bit) & 1) result |= 1ULL << positions[bit];
    }
    return result;
}

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

    int h, w;
    cin >> h >> w;
    if ((h & 1) || (w & 1)) {
        cout << -1 << '\n';
        return 0;
    }

    vector<int> gh = cyclic_gray(h);
    vector<int> gw = cyclic_gray(w);
    auto [pos_h, pos_w] = optimal_bit_positions(h, w);
    vector<unsigned long long> row(h), column(w);
    for (int i = 0; i < h; ++i) row[i] = deposit_bits(gh[i], pos_h);
    for (int j = 0; j < w; ++j) column[j] = deposit_bits(gw[j], pos_w);

    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (j) cout << ' ';
            cout << (row[i] | column[j]);
        }
        cout << '\n';
    }
    return 0;
}