#ifdef NYAOWO
#include "grader.cpp"
#endif
#include "towns.h"
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
mt19937_64 rng(1011101148763ll);
map<pii, int> mem;
int dist(int a, int b) {
if(a > b) swap(a, b);
pii p(a, b);
if(mem.count(p)) return mem[p];
mem[p] = getDistance((int32_t)a, (int32_t)b);
return mem[p];
}
int32_t hubDistance(int32_t N, int32_t sub) {
// remember to init!
mem.clear();
vector<int> al(N);
For(i, 0, N - 1) al[i] = i;
int dia = 0;
int p1 = 0;
shuffle(all(al), rng);
for(auto &i:al) {
int d = dist(i, 0);
if(d > dia) {
dia = d;
p1 = i;
}
}
dia = 0;
int p2 = p1;
shuffle(all(al), rng);
for(auto &i:al) {
int d = dist(p1, i);
if(d > dia) {
dia = d;
p2 = i;
}
}
map<int, int> cnt;
map<int, vector<int>> child;
For(i, 0, N - 1) if(i != p1 && i != p2) {
int d1 = dist(p1, i);
int d2 = dist(p2, i);
int d = (dia + d1 - d2) / 2;
cnt[d]++;
child[d].eb(i);
}
auto check = [&](int d, vector<int> v) {
int jury = v.back(); v.pop_back();
int hp = 1;
for(auto &i:v) {
if(hp == 0) {
jury = i; hp = 1;
} if(d * 2 < dist(p1, jury) + dist(p1, i) - dist(jury, i)) {
hp++;
} else {
hp--;
}
}
hp = 1;
for(auto &i:v) {
if(d * 2 < dist(p1, jury) + dist(p1, i) - dist(jury, i)) {
hp++;
}
}
return hp * 2 > N;
};
int mn = dia;
vector<int> pos, val;
vector<int> pre, suf;
for(auto &i:cnt) {
mn = min(mn, max(i.F, dia - i.F));
pos.eb(i.F);
val.eb(i.S);
pre.eb(0);
suf.eb(0);
}
int m = sz(pos);
pre[0] = 1;
For(i, 1, m - 1) pre[i] = pre[i - 1] + val[i - 1];
suf[m - 1] = 1;
Forr(i, m - 2, 0) suf[i] = suf[i + 1] + val[i + 1];
bool balanced = false;
For(i, 0, m - 1) {
if(max(pos[i], dia - pos[i]) == mn) {
int mx_sub = max({val[i], pre[i], suf[i]});
if(2 * mx_sub <= N) balanced = true;
}
}
if(!balanced) For(i, 0, m - 1) {
if(max(pos[i], dia - pos[i]) == mn) {
if(val[i] * 2 > N && check(pos[i], child[pos[i]])) balanced = true;
}
}
if(!balanced) mn = -mn;
return (int32_t)mn;
}
Compilation message
sorting.cpp:5:10: fatal error: towns.h: No such file or directory
5 | #include "towns.h"
| ^~~~~~~~~
compilation terminated.
