結果

問題 No.3732 Labyrinth Maker
コンテスト
ユーザー 👑 Nachia
提出日時 2026-09-19 13:43:41
言語 C++17
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 119 ms / 2,000 ms
+ 615µs
コード長 2,906 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 696 ms
コンパイル使用メモリ 109,296 KB
実行使用メモリ 58,364 KB
最終ジャッジ日時 2026-09-19 13:44:12
合計ジャッジ時間 27,731 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge4_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
// disable assert
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll INF = 1ll << 60;
#define REP(i,n) for(ll i=0; i<ll(n); i++)
template <class T> using V = vector<T>;
template <class A, class B> void chmax(A& l, const B& r){ if(l < r) l = r; }
template <class A, class B> void chmin(A& l, const B& r){ if(r < l) l = r; }


void testcase(){
  ll N; cin >> N;
  V<V<ll>> A(N, V<ll>(N));
  REP(i,N) REP(j,N) cin >> A[i][j];
  ll sum = 0;
  REP(i,N) REP(j,N) sum += A[i][j];
  if(sum % N != 0){ cout << "-1\n"; return; }
  V<pair<ll,ll>> hamilton;
  hamilton.emplace_back(0,0);
  {
    auto R = [&](){
      auto [u,v] = hamilton.back();
      hamilton.push_back({u,v+1});
    };
    auto L = [&](){
      auto [u,v] = hamilton.back();
      hamilton.push_back({u,v-1});
    };
    auto D = [&](){
      auto [u,v] = hamilton.back();
      hamilton.push_back({u+1,v});
    };
    auto U = [&](){
      auto [u,v] = hamilton.back();
      hamilton.push_back({u-1,v});
    };
    if(N == 3){
      R(); R(); D(); L(); D(); L(); U(); U();
      A[N-2][N-1] += A[N-1][N-1]; A[N-1][N-1] = 0;
    } else if(N%2 == 0){
      REP(i,N/2){
        if(i) D(); else R();
        REP(j,N-2) R();
        D();
        REP(j,N-2) L();
      }
      L();
      REP(i,N-1) U();
    } else {
      REP(i,N/2-1){
        if(i) D(); else R();
        REP(j,N-2) R();
        D();
        REP(j,N-2) L();
      }
      D();
      REP(j,N-2) R();
      D();
      REP(i,N/2){ L(); D(); L(); U(); }
      REP(i,N-2) U();
      A[N-2][N-1] += A[N-1][N-1]; A[N-1][N-1] = 0;
    }
  }
  // REP(i,N){
  //   REP(j,N){
  //     if(j) cout << " ";
  //     cout << (A[i][j]);
  //   } cout << "\n";
  // }
  // for(auto [u,v] : hamilton) cout << u << "," << v << " "; cout << endl;
  hamilton.pop_back();
  V<V<ll>> vis(N, V<ll>(N));
  for(auto [u,v] : hamilton) vis[u][v] += 1;
  // REP(i,N){
  //   REP(j,N) cout << vis[i][j];
  //   cout << "\n";
  // } cout << "\n";
  // cout << "##" << endl;
  ll K = hamilton.size();
  V<ll> sep(K);
  REP(i,K-1) sep[i+1] = (sep[i] + A[hamilton[i].first][hamilton[i].second]) % N;
  // for(auto a : sep) cout << a << " "; cout << endl;
  V<ll> freq(N);
  for(auto h : sep) freq[h]++;
  ll rem = max_element(freq.begin(), freq.end()) - freq.begin();
  // cout << "rem = " << rem << endl;
  V<ll> buf(K+1);
  REP(i,K) if(rem == sep[i]) buf[i] += 1;
  REP(i,K) buf[i+1] = min<ll>(N, buf[i+1] + buf[i]);

  V<V<ll>> ans(N, V<ll>(N));
  REP(i,K) ans[hamilton[i].first][hamilton[i].second] = buf[i] % N;
  if(N%2 == 1) ans[N-1][N-1] = ans[N-2][N-1];
  REP(i,N){
    REP(j,N){
      if(j) cout << " ";
      cout << (ans[i][j] + 1);
    } cout << "\n";
  }
}

int main(){
  cin.tie(0)->sync_with_stdio(0);
  ll T; cin >> T; REP(t,T)
  testcase();
  return 0;
}
0