| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 371286 | Mamnoon_Siam | Towns (IOI15_towns) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
int hubDistance(int N, int sub) {
map<ii, int> mem;
int qcnt = 0;
function<int(int,int)> get = [&mem,&qcnt](int i, int j) {
if(i == j) return 0;
if(i > j) swap(i, j);
if(mem.count(ii(i,j))) return mem[ii(i,j)];
assert(++qcnt <= 5*N);
return mem[ii(i,j)] = getDistance(i,j);
};
function<tuple<int,int,int>(int,int,int)> hands = [&mem,&get](int A, int B, int C) {
int AB = get(A, B), BC = get(B, C), CA = get(C, A);
int a = (AB - BC + CA) / 2;
int b = (BC - CA + AB) / 2;
int c = (CA - AB + BC) / 2;
return make_tuple(a, b, c);
};
ii mx1 = {-1, -1};
for(int i = 1; i < N; ++i) {
mx1 = max(mx1, ii(get(0, i), i));
}
int d1 = mx1.se;
ii mx2 = {-1, -1};
for(int i = 0; i < N; ++i) if(i != d1) {
mx2 = max(mx2, ii(get(d1, i), i));
}
int d2 = mx2.se;
map<int, vi> dia;
for(int i = 0; i < N; ++i) {
dia[std::get<0>(hands(d1, d2, i))].emplace_back(i);
}
int dia_len = get(d1, d2);
int R = INT_MAX;
for(auto x : dia) {
R = min(R, max(x.fi, dia_len - x.fi));
}
int center_cnt = 0;
for(auto x : dia) {
if(max(x.fi, dia_len - x.fi) == R)
center_cnt++;
}
debug(d1, d2);
debug(center_cnt);
function<vi(vi,vi)> add = [](vi a, vi b) {
vi c;
sort(all(a)), sort(all(b));
set_union(all(a), all(b), back_inserter(c));
return c;
};
if(center_cnt == 2) {
int left_cnt = 0, right_cnt = 0;
for(auto x : dia) {
if(x.fi <= dia_len - R) left_cnt += sz(x.se);
else right_cnt += sz(x.se);
}
if(left_cnt == right_cnt) return R;
return -R;
} else if(center_cnt == 1) {
int d12C = -1;
for(auto x : dia) {
if(max(x.fi, dia_len - x.fi) == R) {
d12C = x.fi;
break;
}
}
vi le, ri, mid;
for(auto x : dia) {
if(x.fi < d12C) le = add(le, x.se);
else if(x.fi > d12C) ri = add(ri, x.se);
else mid = add(mid, x.se);
}
if(sz(le) > N/2 or sz(ri) > N/2) return -R;
debug(d12C);
vi candidate;
for(int i : mid) {
debug(i);
if(candidate.empty()) candidate.push_back(i);
else if(std::get<0>(hands(d1, candidate.back(), i)) != d12C)
candidate.push_back(i);
else candidate.pop_back();
}
function<void(vi&,vi&)> pop = [](vi& a, vi& b) {
if(sz(a) > sz(b)) a.resize(sz(a) - sz(b));
else a = vi(b.begin(), b.begin() + sz(b)-sz(a));
};
pop(candidate, le);
pop(candidate, ri);
if(candidate.empty()) return R;
int piv = candidate.back();
if(count(all(le), piv) or count(all(ri), piv)) return R;
int cnt = 0;
for(int i : mid) {
if(std::get<0>(hands(d1, piv, i)) != d12C)
++cnt;
}
if(cnt > N/2) return -R;
return R;
} else {
assert(false);
return 69;
}
}