#1187911 (C++23) No.3739 Stronger Network

• 問題: No.3739 Stronger Network
• ユーザー: uruzunyaa
• 提出日時: 2026-09-19 07:10:42
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 32 ms / 2,000 ms
• コード長: 4,190 bytes
• コンパイル時間: 2,526 ms
• コンパイル使用メモリ: 349,888 KB
• 実行使用メモリ: 9,900 KB
• 最終ジャッジ日時: 2026-09-19 13:27:21
• 合計ジャッジ時間: 6,665 ms
• ジャッジサーバーID （参考情報）: judge6_1 / judge1_1

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

ソースコード

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

using ll = long long;

// 0,1,...,n-1 を全て 1 回ずつ使い、
// 隣接する要素（末尾と先頭も含む）の XOR が必ず 2 冪となる巡回列。
// n は偶数。
vector<int> cyclic_gray(int n) {
    // 2冪なら普通の Gray code
    if ((n & (n - 1)) == 0) {
        vector<int> res(n);
        for (int i = 0; i < n; i++) {
            res[i] = i ^ (i >> 1);
        }
        return res;
    }

    // n = p + r
    // p : n 未満最大の 2 冪
    int p = 1 << (31 - __builtin_clz(n));
    int r = n - p;

    auto c = cyclic_gray(r);

    int a = c[0];
    int b = c[1];

    // a,b が異なる bit
    int k = __builtin_ctz(a ^ b);

    // Q_p における 0 -> 1 Hamilton path を、
    // a -> b Hamilton path に移す変換
    auto trans = [&](int x) {
        // bit 0 と bit k を交換
        if (k != 0 && (((x >> 0) ^ (x >> k)) & 1)) {
            x ^= 1 | (1 << k);
        }
        return x ^ a;
    };

    vector<int> res;
    res.reserve(n);

    // 通常の Gray cycle
    // 0,1,g(2),...,g(p-1),0
    //
    // その 0-1 辺を切ると
    // 0,g(p-1),...,g(2),1
    // が Hamilton path になる
    res.push_back(trans(0));
    for (int i = p - 1; i >= 1; i--) {
        res.push_back(trans(i ^ (i >> 1)));
    }

    // b -> p+b -> ... -> p+a -> a
    for (int i = 1; i < r; i++) {
        res.push_back(p + c[i]);
    }
    res.push_back(p + c[0]);

    return res;
}

// x の i bit目を pos[i] bit目へ移す
ll expand_bits(int x, const vector<int>& pos) {
    ll res = 0;
    for (int i = 0; i < (int)pos.size(); i++) {
        if ((x >> i) & 1) {
            res |= 1LL << pos[i];
        }
    }
    return res;
}

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

    int H, W;
    cin >> H >> W;

    // 奇数長の cycle は hypercube に入らない
    if (H % 2 || W % 2) {
        cout << -1 << '\n';
        return 0;
    }

    // ceil(log2 H), ceil(log2 W)
    int bh = 32 - __builtin_clz(H - 1);
    int bw = 32 - __builtin_clz(W - 1);

    const ll INF = (1LL << 60);

    // dp[i][j]:
    // 下から i 個の縦bit、j 個の横bitを配置したときの最小値
    vector dp(bh + 1, vector<ll>(bw + 1, INF));
    vector how(bh + 1, vector<int>(bw + 1, -1));

    dp[0][0] = 0;

    for (int i = 0; i <= bh; i++) {
        for (int j = 0; j <= bw; j++) {
            if (dp[i][j] == INF) continue;

            int p = i + j;

            // 次の bit を縦用にする
            if (i < bh) {
                ll nd =
                    dp[i][j]
                    + (((H - 1) >> i) & 1LL) * (1LL << p);

                if (nd < dp[i + 1][j]) {
                    dp[i + 1][j] = nd;
                    how[i + 1][j] = 0;
                }
            }

            // 次の bit を横用にする
            if (j < bw) {
                ll nd =
                    dp[i][j]
                    + (((W - 1) >> j) & 1LL) * (1LL << p);

                if (nd < dp[i][j + 1]) {
                    dp[i][j + 1] = nd;
                    how[i][j + 1] = 1;
                }
            }
        }
    }

    // bit の割り当てを復元
    vector<int> order;

    int i = bh;
    int j = bw;

    while (i || j) {
        int t = how[i][j];
        order.push_back(t);

        if (t == 0) i--;
        else j--;
    }

    reverse(order.begin(), order.end());

    vector<int> hpos, wpos;

    for (int p = 0; p < (int)order.size(); p++) {
        if (order[p] == 0) {
            hpos.push_back(p);
        } else {
            wpos.push_back(p);
        }
    }

    // 縦・横それぞれの cyclic Gray code
    auto hr = cyclic_gray(H);
    auto wc = cyclic_gray(W);

    vector<ll> row(H);
    vector<ll> col(W);

    for (int i = 0; i < H; i++) {
        row[i] = expand_bits(hr[i], hpos);
    }

    for (int j = 0; j < W; j++) {
        col[j] = expand_bits(wc[j], wpos);
    }

    // bit 集合が disjoint なので OR = XOR
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (j) cout << ' ';
            cout << (row[i] | col[j]);
        }
        cout << '\n';
    }
}