結果

問題 No.3131 Twin Slide Puzzles
ユーザー cho435
提出日時 2025-04-29 03:38:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,859 bytes
コンパイル時間 3,166 ms
コンパイル使用メモリ 211,868 KB
実行使用メモリ 206,208 KB
最終ジャッジ日時 2025-04-29 03:39:18
合計ジャッジ時間 22,632 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 1
other AC * 19 WA * 38
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <algorithm>
#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);
	auto print_p = [&](vector<int> p) {
		if ((int)p.size() < n * n) {
			p.resize(n * n);
			rep(i, m * m, n * n) {
				p[i] = i;
			}
		}
		rep(i, 0, n) {
			rep(j, 0, n) cout << p[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 * n + j] == 0) {
				ad = (i + j) & 1;
			}
		}
		vector<int> rp(m * m);
		rep(i, 0, m * m) rp[p[i]] = i;
		rep(i, 0, m * m) {
			if (p[i] != i) {
				swap(p[rp[i]], p[i]);
				rp[p[rp[i]]] = rp[i];
				rp[i] = i;
				ad = (ad + 1) & 1;
			}
		}
		return ad;
	};
	vector<int> p(m * m);
	iota(p.begin(), p.end(), 0);
	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 * n + 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