結果

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

ソースコード

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];
	auto print_p = [&](const vector<int>& p) {
		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, n) rep(j, 0, n) {
			if (p[i * n + j] == 0) {
				ad = (i + j) & 1;
			}
		}
		rep(i, 0, n * n) {
			if (p[i] != i) {
				swap(p[i], p[p[i]]);
				ad = (ad + 1) & 1;
			}
		}
		return ad;
	};
	vector<int> p(n * n);
	iota(p.begin(), p.end(), 0);
	map<ll, vector<int>> mp;
	do {
		if (check_p(p)) continue;
		ll tmp = 0;
		rep(i, 0, n) {
			rep(j, 0, n) 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