結果

問題 No.3724 Domination
コンテスト
ユーザー cho435
提出日時 2026-09-19 17:25:50
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 51 ms / 2,000 ms
+ 897µs
コード長 3,944 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,795 ms
コンパイル使用メモリ 365,948 KB
実行使用メモリ 10,040 KB
最終ジャッジ日時 2026-09-19 17:26:16
合計ジャッジ時間 13,451 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
サブタスク 配点 結果
部分点 20 % AC * 8
満点 80 % AC * 52
合計 2.5 * 100% = 250 点
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

void solve() {
	int n;
	cin >> n;
	vector<int> r(n), c(n);
	rep(i, 0, n) cin >> r[i], r[i]--;
	rep(i, 0, n) cin >> c[i], c[i]--;

	auto reorder = [&](vector<vector<int>> ans) {
		vector<vector<int>> nans;
		{
			vector<vector<int>> nr(n);
			rep(i, 0, n) {
				vector<int> cnt(n);
				rep(j, 0, n) cnt[ans[i][j]]++;
				int x = max_element(all(cnt)) - cnt.begin();
				nr[x].push_back(i);
			}
			rep(i, 0, n) {
				nans.push_back(ans[nr[r[i]].back()]);
				nr[r[i]].pop_back();
			}
			swap(ans, nans);
		}
		{
			vector<vector<int>> nc(n);
			rep(j, 0, n) {
				vector<int> cnt(n);
				rep(i, 0, n) cnt[ans[i][j]]++;
				int x = max_element(all(cnt)) - cnt.begin();
				nc[x].push_back(j);
			}
			rep(j, 0, n) {
				int nj = nc[c[j]].back();
				nc[c[j]].pop_back();
				rep(i, 0, n) nans[i][j] = ans[i][nj];
			}
		}
		return nans;
	};

	auto build_per = [&]() {
		vector<vector<int>> ans(n, vector<int>(n, -1));
		vector<int> rr(n), rc(n);
		rep(i, 0, n) rr[r[i]] = i;
		rep(i, 0, n) rc[c[i]] = i;
		rep(i, 0, n) {
			ans[rr[i]][rc[i]] = i;
			ans[rr[(i + 1) % n]][rc[i]] = i;
			ans[rr[i]][rc[(i + 1) % n]] = i;
			if (n == 4) ans[rr[i]][rc[(i + 2) % n]] = i;
		}
		return ans;
	};
	if (n == 1) {
		cout << "1\n";
		return;
	}
	if (n == 2) {
		cout << "-1\n";
		return;
	}
	if (n == 3) {
		if (c[0] == c[1] && c[0] == c[2]) {
			cout << "-1\n";
			return;
		}
		if ((c[0] ^ c[1] ^ c[2]) == 3) {
			vector<vector<int>> ans = {
				{0, 0, 1},
				{2, 1, 1},
				{2, 0, 2},
			};
			ans = reorder(ans);
			rep(i, 0, n) {
				rep(j, 0, n) cout << ans[i][j] + 1 << ' ';
				cout << '\n';
			}
			return;
		}
		vector<vector<int>> ans = {
			{0, 0, 1},
			{0, 1, 1},
			{2, 0, 2},
		};
		vector<int> cc(n);
		rep(i, 0, n) cc[c[i]]++;
		vector<int> to(n, -1);
		rep(i, 0, n) {
			if (cc[i] == 0) to[2] = i;
			if (cc[i] == 1) to[1] = i;
			if (cc[i] == 2) to[0] = i;
		}
		rep(i, 0, n) rep(j, 0, n) ans[i][j] = to[ans[i][j]];
		ans = reorder(ans);
		rep(i, 0, n) {
			rep(j, 0, n) cout << ans[i][j] + 1 << ' ';
			cout << '\n';
		}
		return;
	}
	if (n == 4) {
		int sz = (int)set<int>(all(c)).size();
		if (sz == n) {
			auto ans = build_per();
			rep(i, 0, n) {
				rep(j, 0, n) cout << ans[i][j] + 1 << ' ';
				cout << '\n';
			}
			return;
		}
		if (sz == 1) {
			cout << "-1\n";
			return;
		}
		vector<vector<int>> ans;
		vector<int> cc(n);
		rep(i, 0, n) cc[c[i]]++;
		vector<vector<int>> cnt(n);
		if (sz == 2) {
			if (ranges::max(cc) == 3) {
				ans = {
					{0, 0, 0, 0},
					{1, 1, 0, 1},
					{0, 2, 1, 2},
					{3, 0, 3, 1},
				};
				cnt[0] = {2, 3};
				cnt[1] = {1};
				cnt[3] = {0};
			} else {
				ans = {
					{0, 0, 0, 0},
					{1, 1, 1, 1},
					{0, 2, 1, 2},
					{3, 0, 3, 1},
				};
				cnt[0] = {2, 3};
				cnt[2] = {0, 1};
			}
		} else {
			ans = {
				{0, 0, 0, 0},
				{1, 0, 1, 2},
				{2, 2, 2, 2},
				{0, 3, 1, 3},
			};
			cnt[0] = {3};
			cnt[1] = {1, 2};
			cnt[2] = {0};
		}
		vector<int> to(n, -1);
		rep(i, 0, n) {
			to[cnt[cc[i]].back()] = i;
			cnt[cc[i]].pop_back();
		}
		rep(i, 0, n) rep(j, 0, n) ans[i][j] = to[ans[i][j]];

		ans = reorder(ans);
		rep(i, 0, n) {
			rep(j, 0, n) cout << ans[i][j] + 1 << ' ';
			cout << '\n';
		}
		return;
	}

	vector<vector<int>> ans(n, vector<int>(n, -1));

	rep(i, 0, n) {
		rep(j, 0, n - 2) {
			ans[i][(i + j) % n] = r[i];
		}
	}
	rep(j, 0, n) {
		rep(i, 0, n) if (ans[i][j] == -1) ans[i][j] = c[j];
	}

	rep(i, 0, n) {
		rep(j, 0, n) cout << ans[i][j] + 1 << ' ';
		cout << '\n';
	}
}

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