結果

問題 No.3131 Twin Slide Puzzles
コンテスト
ユーザー cho435
提出日時 2025-04-29 03:56:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,124 ms / 4,000 ms
コード長 1,997 bytes
コンパイル時間 2,613 ms
コンパイル使用メモリ 213,332 KB
実行使用メモリ 228,096 KB
最終ジャッジ日時 2025-06-20 02:55:14
合計ジャッジ時間 36,420 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <ctime>
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 <typename T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <typename T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

struct IOST {
	IOST() {
		ios::sync_with_stdio(false);
		cin.tie(nullptr);
		cout << fixed << setprecision(20);
	}
} IOST;

int timer() {
	static auto st = chrono::system_clock::now();
	auto en = chrono::system_clock::now();
	return chrono::duration_cast<chrono::milliseconds>(en - st).count();
}

void solve() {
	timer();
	int n;
	cin >> n;
	vector<vector<ll>> a(n, vector<ll>(n));
	rep(i, 0, n) rep(j, 0, n) cin >> a[i][j];
	int m = min(4, n);
	vector<pair<int, int>> rp(n * n);
	auto print_p = [&](vector<int> p) {
		rep(i, 0, n) {
			rep(j, 0, n) {
				if (i < m && j < m) cout << p[i * m + j] << " ";
				else cout << i * n + j << " ";
			}
			cout << "\n";
		}
	};
	auto check_p = [&](vector<int> p) {
		int ad = 0;
		rep(i, 0, m) rep(j, 0, m) {
			if (p[i * m + j] == 0) {
				ad = (i + j) & 1;
			}
		}
		rep(i, 0, m) rep(j, 0, m) rp[p[i * m + j]] = {i, j};
		rep(i, 0, m) rep(j, 0, m) {
			if (p[i * m + j] != i * n + j) {
				auto [x, y] = rp[i * n + j];
				swap(p[i * m + j], p[x * m + y]);
				rp[p[i * m + j]] = {i, j};
				rp[p[x * m + y]] = {x, y};
				ad = (ad + 1) & 1;
			}
		}
		return ad;
	};
	vector<int> p(m * m);
	rep(i, 0, m) rep(j, 0, m) {
		p[i * m + j] = i * n + j;
	}
	map<ll, vector<int>> mp;
	do {
		if (check_p(p)) continue;
		ll tmp = 0;
		rep(i, 0, m) {
			rep(j, 0, m) tmp += a[i][j] * p[i * m + j];
		}
		if (mp.count(tmp)) {
			cout << "Yes\n";
			print_p(p);
			print_p(mp[tmp]);
			return;
		}
		mp[tmp] = p;
		if (timer() > 3500) break;
	} while (next_permutation(p.begin(), p.end()));
	cout << "No\n";
}

int main() {
	int t = 1;
	// cin >> t;
	rep(i, 0, t) solve();
}
0