Contest Duration: ~ (local time) (120 minutes) Back to Home

Submission #5938860

Source Code Expand

Copy
```#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <chrono>
#include <assert.h>
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());

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

// rand-function that works properly on windows, and is faster than rand
// https://codeforces.com/blog/entry/61587
template<class T>
T rand(T a, T b) {
return uniform_int_distribution<T>(a, b)(rng);
}

const ll MAX_V = 1e10;

ll log2(int v) {
int res = 1;
while(v > 1) {
v /= 2;
++res;
}
return res;
}

// Find 9 numbers s.t. their sum is distinct
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;
while(true) {
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]);
}
/*
for (int i = 0; i < n; ++i) {
for (j = i+1; j < n; ++j) {
if (rand(0, 1)) cost[i][j] = rand(1ll, MAX_V);
cost[j][i] = cost[i][j];
}
}
*/
if (works()) {
for (int i = 0; i < n; ++i) {
for (j = 0; j < n; ++j) {
cout << cost[i][j] << ' ';
}
cout << '\n';
}
break;
}
}
}
```

#### Submission Info

Submission Time 2019-06-15 23:25:54+0900 F - Diverta City mangolassi C++14 (GCC 5.4.1) 900 1989 Byte AC 290 ms 17896 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
All 900 / 900 in1.txt, in2.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
in1.txt 1 ms 256 KB
in2.txt 1 ms 256 KB
in3.txt 1 ms 256 KB
in4.txt 1 ms 256 KB
in5.txt 4 ms 640 KB
in6.txt 28 ms 2420 KB
in7.txt 290 ms 17896 KB
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB