#1170748 (C++23(gcc16)) No.3732 Labyrinth Maker

• 問題: No.3732 Labyrinth Maker
• ユーザー: 👑 kencho
• 提出日時: 2026-07-10 19:39:51
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,533 bytes
• コンパイル時間: 3,360 ms
• コンパイル使用メモリ: 361,160 KB
• 実行使用メモリ: 20,864 KB
• 最終ジャッジ日時: 2026-09-19 12:34:51
• 合計ジャッジ時間: 27,951 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 53 WA * 6

ソースコード

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

void solveCase() {
    int N;
    cin >> N;

    int M = N * N;

    vector<int> A(M);
    int total = 0;

    auto id = [&](int i, int j) {
        return i * N + j;
    };

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int x;
            cin >> x;
            A[id(i, j)] = x % N;
            total += A[id(i, j)];
            total %= N;
        }
    }

    if (total != 0) {
        cout << -1 << '\n';
        return;
    }

    vector<int> order;
    order.reserve(M);

    if (N % 2 == 0) {
        // 0 行目を左から右へ
        for (int j = 0; j < N; j++) {
            order.push_back(id(0, j));
        }

        // 1 行目以降、0 列目を除いて snake
        for (int i = 1; i < N; i++) {
            if (i % 2 == 1) {
                for (int j = N - 1; j >= 1; j--) {
                    order.push_back(id(i, j));
                }
            } else {
                for (int j = 1; j < N; j++) {
                    order.push_back(id(i, j));
                }
            }
        }

        // 0 列目を下から上へ
        for (int i = N - 1; i >= 1; i--) {
            order.push_back(id(i, 0));
        }
    } else {
        // 0 行目を左から右へ
        for (int j = 0; j < N; j++) {
            order.push_back(id(0, j));
        }

        // N-1 列目から 2 列目までを縦 snake
        for (int j = N - 1; j >= 2; j--) {
            int k = (N - 1) - j;

            if (k % 2 == 0) {
                for (int i = 1; i < N; i++) {
                    order.push_back(id(i, j));
                }
            } else {
                for (int i = N - 1; i >= 1; i--) {
                    order.push_back(id(i, j));
                }
            }
        }

        // 最後に 1,0 列目を下から上へ zigzag
        for (int i = N - 1; i >= 1; i--) {
            int k = (N - 1) - i;

            if (k % 2 == 0) {
                order.push_back(id(i, 1));
                order.push_back(id(i, 0));
            } else {
                order.push_back(id(i, 0));
                order.push_back(id(i, 1));
            }
        }
    }

    // prefix sum mod N ごとに切断点を分類する
    vector<vector<int>> pos(N);

    int s = 0;

    for (int t = 0; t < M; t++) {
        // 奇数であっても全ての箇所で切断可能としてしまう
        pos[s].push_back(t);

        s += A[order[t]];
        if (s >= N) s -= N;
    }

    int cls = -1;

    for (int r = 0; r < N; r++) {
        if ((int)pos[r].size() >= N) {
            cls = r;
            break;
        }
    }

    // total == 0 なら必ず見つかる
    if (cls == -1) {
        cout << -1 << '\n';
        return;
    }

    vector<int> cut;
    for (int i = 0; i < N; i++) {
        cut.push_back(pos[cls][i]);
    }

    vector<int> ans(M, 0);

    // cut[i] から cut[i+1] の直前までを部屋 i+1 にする
    for (int k = 0; k < N; k++) {
        int l = cut[k];
        int r = cut[(k + 1) % N];

        if (k == N - 1) {
            r += M;
        }

        for (int x = l; x < r; x++) {
            ans[order[x % M]] = k + 1;
        }
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (j) cout << ' ';
            cout << ans[id(i, j)];
        }
        cout << '\n';
    }
}

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

    int T;
    cin >> T;
    while (T--) solveCase();
    return 0;
}