#1185872 (C++23) No.3747 Hamming Distance on Torus

• 問題: No.3747 Hamming Distance on Torus
• ユーザー: Naru820
• 提出日時: 2026-09-11 14:38:47
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 2 ms / 2,000 ms
• コード長: 3,812 bytes
• コンパイル時間: 1,316 ms
• コンパイル使用メモリ: 179,132 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-09-25 20:52:12
• 合計ジャッジ時間: 3,616 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

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

ソースコード

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;

// Returns an empty vector if construction is impossible.
vector<string> construct(int n, int A, int B) {
    const bool flipRows = A > n / 2;
    const bool flipCols = B > n / 2;
    int a = min(A, n - A);
    int b = min(B, n - B);
    const bool transpose = a > b;
    if (transpose) swap(a, b);

    vector<string> grid(n, string(n, '0'));
    int column = 0;

    // Nonzero columns occupy indices 0, 2, 4, ... .
    // All odd-indexed columns remain zero.
    auto addColumn = [&](const string& v, int shift) {
        for (int i = 0; i < n; ++i)
            grid[i][column] = v[(i + shift) % n];
        column += 2;
    };

    if (a == 0) {
        if (b != 0) return {};
    } else if (a == 1) {
        const int g = gcd(n, b);
        const int length = n / g;
        if (length % 2 != 0) return {};

        // Match consecutive vertices in each cycle of x -> x + b.
        for (int start = 0; start < g; ++start) {
            int u = start;
            for (int k = 0; k < length; k += 2) {
                string v(n, '0');
                for (int j = 1; j <= b; ++j)
                    v[(u + j) % n] = '1';
                addColumn(v, 0);
                u = (u + 2 * b) % n;
            }
        }
    } else if (a % 2 == b % 2) {
        // a runs of ones and a runs of zeros, all of odd length.
        string v(b - a + 1, '1');
        for (int k = 0; k < a - 1; ++k) v += "01";
        v += string(n - b - a + 1, '0');

        for (int shift = 0; shift < n; shift += 2)
            addColumn(v, shift);
    } else {
        if (n % 4 != 0) return {};

        // Find v of weight b with a transitions on residues {0, 1}
        // and a transitions on residues {2, 3} modulo 4.
        string v;
        for (int firstRun = 1; firstRun <= 2 && v.empty(); ++firstRun) {
            string candidate;
            for (int k = 0; k < a; ++k) {
                int ones = 1;
                if (k == 0) ones = firstRun;
                if (k == 1) ones = b - a + 2 - firstRun;
                candidate += string(ones, '1');
                int zeros = (k + 1 == a ? n - b - a + 1 : 1);
                candidate += string(zeros, '0');
            }

            int changes[4] = {};
            for (int i = 0; i < n; ++i)
                if (candidate[i] != candidate[(i + 1) % n])
                    ++changes[i % 4];

            for (int shift = 0; shift < 4; ++shift) {
                if (changes[shift] + changes[(shift + 1) % 4] == a) {
                    v = candidate.substr(shift) + candidate.substr(0, shift);
                    break;
                }
            }
        }
        assert(!v.empty());

        string w(n, '0');
        for (int i = 0; i < n; ++i) w[i] = v[(n + 2 - i) % n];
        for (int shift = 0; shift < n; shift += 4) {
            addColumn(v, shift);
            addColumn(w, shift);
        }
    }

    // Undo normalization, first transposing, then flipping rows/columns.
    if (transpose)
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                swap(grid[i][j], grid[j][i]);

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            bool flip = (flipRows && i % 2) ^ (flipCols && j % 2);
            if (flip) grid[i][j] = (grid[i][j] == '0' ? '1' : '0');
        }
    }
    return grid;
}

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

    int T;
    cin >> T;
    while (T--) {
        int N, A, B;
        cin >> N >> A >> B;
        auto answer = construct(N, A, B);
        if (answer.empty()) cout << -1 << '\n';
        else for (const auto& row : answer) cout << row << '\n';
    }
    return 0;
}