#1188718 (C++17) No.3732 Labyrinth Maker

• 問題: No.3732 Labyrinth Maker
• ユーザー: jupiter_68
• 提出日時: 2026-09-19 15:13:24
• 言語: C++17 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 3,872 bytes
• コンパイル時間: 1,195 ms
• コンパイル使用メモリ: 219,740 KB
• 実行使用メモリ: 19,072 KB
• 最終ジャッジ日時: 2026-09-19 15:14:03
• 合計ジャッジ時間: 25,533 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge5_0

ファイルパターン	結果
sample	AC * 1
other	AC * 16 WA * 19 RE * 24

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pll = array<ll, 2>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define all(a) (a).begin(),(a).end()
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define reps(i, l, r) for(ll i = (l); i < (r); ++i)
#define rrep(i, l, r) for(ll i = (r)-1; i >= (l); --i)
#define sz(x) (ll) (x).size()
template <typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }

const ll mod = 998244353; // 1000000007;

struct mint {
    ll x;
    mint(ll y = 0) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    mint &operator+=(const mint &p) {
        if ((x += p.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator-=(const mint &p) {
        if ((x += mod - p.x) >= mod) x -= mod;
        return *this;
    }
    mint &operator*=(const mint &p) {
        x = (ll)(1ll * x * p.x % mod);
        return *this;
    }
    mint &operator/=(const mint &p) {
        *this *= p.inv();
        return *this;
    }
    mint operator-() const { return mint(-x); }
    mint operator+(const mint &p) const { return mint(*this) += p; }
    mint operator-(const mint &p) const { return mint(*this) -= p; }
    mint operator*(const mint &p) const { return mint(*this) *= p; }
    mint operator/(const mint &p) const { return mint(*this) /= p; }
    bool operator==(const mint &p) const { return x == p.x; }
    bool operator!=(const mint &p) const { return x != p.x; }
    friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; }
    friend istream &operator>>(istream &is, mint &a) {
        ll t; is >> t; a = mint(t); return (is);
    }
    mint inv() const { return pow(mod - 2); }
    mint pow(ll n) const {
        mint ret(1), mul(x);
        while (n > 0) {
            if (n & 1) ret *= mul;
            mul *= mul;
            n >>= 1;
        }
        return ret;
    }
};

void solve(){
    ll N; cin >> N;
    vv<ll> a(N, vl(N));
    rep(i, N){
        rep(k, N) cin >> a[i][k];
    }
    ll sum = 0;
    rep(i, N){
        rep(k, N) sum += a[i][k];
    }
    if(sum % N != 0){
        cout << -1 << endl;
        return;
    }
    vv<ll> ans(N, vl(N, -1));
    ll L = 0, R = 0;
    rep(i, N-1){
        vl v = a[i];
        v[0] += L, v[N-1] += R;
        vl s(N+1, 0); rep(k, N) s[k+1] = s[k] + v[k];
        vl idx(N, -1); idx[0] = 0;
        ll l = 0, r = N;
        rep(k, N){
            ll x = s[k+1] % N;
            if(x == 0){
                l = 0, r = k+1;
                break;
            }
            if(idx[x] == -1) idx[x] = k+1;
            else{
                l = idx[x], r = k+1;
                break;
            }
        }
        reps(t, l, r) ans[i][t] = i+1;
        if(l == 0) L = 0;
        else L += s[l];
        if(r == N) R = 0;
        else R += s[N] - s[r];
    }
    ll cL = N, cR = N;
    rep(k, N) ans[N-1][k] = N;
    rrep(i, 0, N-1){
        if(ans[i][0] != -1) cL = ans[i][0];
        else{
            rep(k, N){
                if(ans[i][k] == -1) ans[i][k] = cL;
                else break;
            }
        }
        if(ans[i][N-1] != -1) cR = ans[i][N-1];
        else{
            rrep(k, 0, N){
                if(ans[i][k] == -1) ans[i][k] = cR;
                else break;
            }
        }
    }
    rep(i, N){
        rep(k, N){
            cout << ans[i][k] << " \n"[k == N-1];
        }
    }
    return;
}

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}