Submission #5939314

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

const int N = 10;
bool visited[N];
vector<ll> vals;
ll cost[N][N];
int n, j;

void dfs(int i, ll s) {
	visited[i] = true;
	int outs = 0;
	for (int t = 0; t < n; ++t) {
		if (! visited[t]) {
			++outs;
			dfs(t, s + cost[i][t]);
		}
	}
	if (outs == 0 && i > j) vals.push_back(s);
	visited[i] = false;
}

bool works() {
	for (j = 0; j+1 < n; ++j) dfs(j, 0);
	sort(vals.begin(), vals.end());
	cerr << vals.back() << '\n';

	bool ans = true;
	for (int i = 0; i+1 < vals.size(); ++i) {
		if (vals[i] == vals[i+1]) ans = false;
	}
	vals.clear();
	return ans;
}

int main() {
	vector<vector<int>> xr = {
	{1},
	{1,2},
	{1,2,4},
	{1,2,4,7},
	{1,2,4,7,12},
	{1,2,4,8,13,18},
	{1,2,4,8,14,19,24},
	{1,2,4,8,15,24,29,34},
	{1,7,10,13,21,26,41,43,45}
	};

	cin >> n;
	ll b = 1;
	for (int i = 0; i+1 < n; ++i) {
		for (j = i+1; j < n; ++j) {
			cost[i][j] = b * xr[n-2-i][j-1-i];
			cost[j][i] = cost[i][j];
		}
		if (i+2 < n) b *= (xr[n-2-i][n-2-i] + xr[n-2-i][n-3-i]);
	}
	if (works()) {
		for (int i = 0; i < n; ++i) {
			for (j = 0; j < n; ++j) {
				cout << cost[i][j] << ' ';
			}
			cout << '\n';
		}
	} else cout << "QAQ\n";
}

Submission Info

Judge Result