Submission #1217232

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217232		Lemser	Towns (IOI15_towns)	C++20	In queue	0 ms	0 KiB

towns

#include "towns.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC target("popcnt")
using namespace std;
 
using ll = long long;
using ull = unsigned long long;
using lld = long double;
using ii = pair<int,int>;
using pll = pair<ll, ll>;
 
using vi = vector<int>;
using vll = vector<ll>;
using vii = vector<ii>;
using vpll = vector<pll>;
using vlld = vector<lld>;
 
#define all(x) x.begin(),x.end()
#define lsb(x) x&(-x)
#define gcd(a,b) __gcd(a,b)
#define sz(x) (int)x.size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fls cout.flush()
 
#define fore(i, l, r) for (auto i = l; i < r; i++)
#define fo(i, n) fore (i, 0, n)
#define forex(i, r, l) for (auto i = r-1; i >= l; i--)
#define ffo(i, n) forex (i, n, 0)
 
bool cmin(ll &a, ll b) { if (b < a) { a=b; return 1; } return 0; }
bool cmax(ll &a, ll b) { if (b > a) { a=b; return 1; } return 0; }

/*
getDistance (i, j)
*/
const int INF = 1e9;

vector<int> d_0, d_a, d_x;

set<ll> cmp1, cmp2;

bool same (ll i, ll j) {
	if (cmp1.count(i) && cmp1.count(j)) return 1;
	if (cmp2.count(i) && cmp2.count(j)) return 1;
	if (cmp1.count(i) || cmp1.count(j) || cmp2.count(i) || cmp2.count(j)) return 0;
	return (getDistance(i, j) < d_a[i] + d_a[j] - 2ll*d_x[i]);
}

int solve (vector<int> vec) {
	// cout << "Solve\n";
	// for (ll i: cmp1) cout << i << ' ';
	// cout << '\n';
	// for (ll i: cmp2) cout << i << ' ';
	// cout << '\n';
	// for (ll i: vec) cout << i << ' ';
	// cout << '\n';
	// return 0 ;
	vector<int> A, B;
	for (ll i: vec) {
		if (A.size() == 0) {
			A.pb(i);
			continue;
		}
		if (same(A.back(), i)) {
			B.pb(i);
			continue;
		}
		A.pb(i);
		if (B.size()) {
			A.pb(B.back());
			B.pop_back();
		}
	}
	// for (ll i: A) cout << i << ' '; 
	// cout << '\n';
	// for (ll i: B) cout << i << ' '; 
	// cout << '\n';
	ll m = A.back();
	while (A.size()) {
		if (A.back() == m || same(A.back(), m)) {
			if (A.size() == 1) {
				B.push_back(A.back());
				A.pop_back();
				continue;
			}
			A.pop_back();
			A.pop_back();
		} else {
			A.pop_back();
			if (B.size() == 0) return 0;
			B.pop_back();
		}
	}
	return (B.size() > 0 ? 1 : 0);
}

int hubDistance(int N, int sub) {
	cmp1.clear();
	cmp2.clear();
	int a, b;
	d_0 = vector<int>(N, 0);
	d_a = vector<int>(N, 0);
	d_x = vector<int>(N, 0);
	for (int i = 1; i < N; i++) d_0[i] = getDistance(0, i);
	for (int i = 0; i < N; i++) if (d_0[i] == *max_element(all(d_0))) {
		a = i;
		break;
	}
	d_a[0] = d_0[a];
	for (int i = 1; i < N; i++) {
		if (i == a) continue;
		d_a[i] = getDistance (a, i);
	}
	for (int i = 0; i < N; i++) if (d_a[i] == *max_element(all(d_a))) {
		b = i;
		break;
	}
	int R = INF, mid = (d_a[0] + d_a[b] - d_0[b])/2;
	map<int, vector<int>> mp;
	for (int i = 0; i < N; i++) {
		d_x[i] = (d_a[i] + d_a[0] - d_0[i])/2;
		R = min(R, max(d_x[i], d_a[b]-d_x[i]));
		if (d_x[i] > mid || i == a || i == b) continue;
		mp[d_x[i]].pb(i);
	}
	ll sum = 1;
	for (auto [k, vec]: mp) {
		ll t = vec.size();
		if (sum > N/2) break;
		if (N - sum - t > N/2 || max(k, d_a[b] - k) > R) {
			sum += t;
			continue;
		}
		fo (i, N) {
			if (d_x[i] == k) continue;
			if (d_x[i] < k) cmp1.insert(i);
			else cmp2.insert(i);
		}
		vector<int> vec2;
		fo (i, N) vec2.pb(i);
		if (t <= N/2) return R;
		if (solve(vec2)) return -R;
		return R;
		sum += t;
	}
	return -R;
}