結果

問題 No.3732 Labyrinth Maker
コンテスト
ユーザー mono
提出日時 2026-09-19 16:09:47
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 3,479 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,523 ms
コンパイル使用メモリ 398,828 KB
実行使用メモリ 50,400 KB
最終ジャッジ日時 2026-09-19 16:10:25
合計ジャッジ時間 33,243 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 39 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#pragma GCC optimize ("O3,inline,omit-frame-pointer,no-asynchronous-unwind-tables,fast-math")
#include <bits/stdc++.h>
#include <unordered_map>
#include <stdlib.h>
using namespace std;
#define rep(i, a, n) for(ll i = a; i < n; i++)
#define rrep(i, a, n) for(ll i = a; i >= n; i--)
#define inr(l, x, r) (l <= x && x < r)
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
//constexpr ll MOD = 1000000007;
constexpr ll MOD = 998244353;
constexpr int IINF = 1001001001;
constexpr ll INF = 1LL<<60;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

void solve(){
    ll n; cin >> n;
    vector<vector<ll>> a(n,vector<ll>(n));
    rep(i,0,n)rep(j,0,n) cin >> a[i][j];
    if(n%2 == 0){
        vector<pll> path;
        ll all = n*n;
        path.reserve(all);
        rep(i,0,n) path.push_back({i,0});
        rrep(i,n-1,0){
            if(i%2 == 1){
                rep(j,1,n) path.push_back({i,j});
            }else{
                rrep(j,n-1,1) path.push_back({i,j});
            }
        }
        vector<ll> sum(all*2+1);
        rep(i,0,all*2) sum[i+1] = (sum[i]+a[path[i%all].first][path[i%all].second])%n;
        vector<ll> cnt(n,0), first(n,INF);
        rep(i,0,all+1){
            cnt[sum[i]]++;
            chmin(first[sum[i]],i);
        }
        vector<vector<ll>> ans(n,vector<ll>(n));
        rep(i,0,n){
            if(cnt[i] <= n) continue;
            ll start = first[i], now = 1, id = start;
            while(id < start+all){
                if(id != start && sum[id] == i && now < n) now++;
                auto [x,y] = path[id%all];
                // cerr << id << " " << x << " " << y << " " << now << endl;
                ans[x][y] = now;
                id++;
            }
            rep(j,0,n){
                rep(k,0,n) cout << ans[j][k] << " ";
                cout << endl;
            }
            break;
        }
    }else{
        vector<pll> path;
        ll all = n*(n-1)+2;
        path.reserve(all);
        rep(i,0,n) path.push_back({i,0});
        rep(i,2,n) a[n-2][n-1] += a[n-1][i];
        path.push_back({n-1,1});
        rrep(i,n-2,0){
            if(i%2 == 1){
                rep(j,1,n) path.push_back({i,j});
            }else{
                rrep(j,n-1,1) path.push_back({i,j});
            }
        }
        vector<ll> sum(all*2+1);
        rep(i,0,all*2) sum[i+1] = (sum[i]+a[path[i%all].first][path[i%all].second])%n;
        vector<ll> cnt(n,0), first(n,INF);
        rep(i,0,all){
            cnt[sum[i]]++;
            chmin(first[sum[i]],i);
        }
        vector<vector<ll>> ans(n,vector<ll>(n));
        rep(i,0,n){
            if(cnt[i] < n) continue;
            ll start = first[i], now = 1, id = start;
            while(id < start+all){
                if(id != start && sum[id] == i && now < n) now++;
                auto [x,y] = path[id%all];
                // cerr << id << " " << x << " " << y << " " << now << endl;
                ans[x][y] = now;
                id++;
            }
            rep(j,2,n) ans[n-1][j] = ans[n-2][n-2];
            rep(j,0,n){
                rep(k,0,n) cout << ans[j][k] << " ";
                cout << endl;
            }
            break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll t; cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
0