제출 #1109714

#제출 시각아이디문제언어결과실행 시간메모리
1109714jerzyk도시들 (IOI15_towns)C++17
100 / 100
21 ms1008 KiB
#include <bits/stdc++.h> #include "towns.h" using namespace std; #define pb push_back #define st first #define nd second typedef long long ll; typedef long double ld; const ll I = 1000'000'000'000'000'000LL; const int II = 2'000'000'000; const ll M = 1000'000'007LL; const int AN = 1007; int vis[AN]; int dis[2][AN]; int centd; void Clean(int n) { centd = 0; for(int r = 0; r < 2; ++r) for(int i = 0; i < n + 3; ++i) dis[r][i] = 0; for(int i = 0; i < n; ++i) vis[i] = 0; } void Do(int n, int &a, int &b) { pair<int, int> ma = make_pair(-1, -1); for(int i = 1; i < n; ++i) { dis[0][i] = getDistance(0, i); ma = max(ma, make_pair(dis[0][i], -i)); } a = -ma.nd; dis[1][0] = ma.st; ma = make_pair(dis[1][0], 0); for(int i = 1; i < n; ++i) { if(i == a) continue; dis[1][i] = getDistance(a, i); ma = max(ma, make_pair(dis[1][i], -i)); } b = -ma.nd; } void Fix(vector<int> &a) { vector<int> nw; sort(a.begin(), a.end()); for(int i = 0; i < (int)a.size(); ++i) if(i == 0 || a[i] != a[i - 1]) nw.pb(a[i]); a = nw; } int D(int x) { return (dis[1][0] + dis[1][x] - dis[0][x]) / 2; } int Dc(int x) { int ans = dis[1][x] - D(x); int dod = D(x) - centd; if(dod < 0) dod *= -1; return ans + dod; } bool Cp(int a, int b) { return (getDistance(a, b) != Dc(a) + Dc(b)); } bool Check(int n) { //cerr << "\n\n"; int cur = 0; vector<int> v; for(int i = 0; i < n; ++i) { if(v.size() == 0) { v.pb(i); ++cur; vis[i] = cur; continue; } if(Cp(v[0], i)) { v.pb(i); vis[i] = cur; }else { v.pop_back(); } } //for(int i = 0; i < n; ++i) //cerr << "V: " << i << " " << vis[i] << " " << Dc(i) << "\n"; if(v.size() == 0) return true; int il = 0, u = v[0]; for(int i = 0; i < n; ++i) { if(vis[i] == -1) continue; if(vis[i] == vis[u]) {++il; continue;} if(vis[i] == 0) { if(Cp(u, i)) ++il; continue; } bool czy = Cp(u, i); if(czy) ++il; for(int j = i + 1; j < n; ++j) if(vis[j] == vis[i]) { vis[j] = -1; if(czy) ++il; } } if(il <= (n / 2)) return true; return false; } int hubDistance(int _NN, int _sub) { //cerr << "\n"; Clean(_NN); int n = _sub; n = _NN; int a, b; Do(n, a, b); vector<int> pth; int xd = D(b); for(int i = 0; i < n; ++i) { int cur = D(i); if(cur <= xd) pth.pb(cur); //cerr << i << " " << D(i) << "\n"; } //cerr << a << " " << b << " xd " << xd << "\n"; Fix(pth); int ans = II; int pos = -1; for(int i = 0; i < (int)pth.size(); ++i) { if(max(pth[i], dis[1][b] - pth[i]) < ans) pos = i; ans = min(ans, max(pth[i], dis[1][b] - pth[i])); } int il = 0; for(int i = 0; i < n; ++i) if(D(i) <= pth[pos]) ++il; if(il <= (n / 2) && pos < (int)pth.size() - 1 && ans == max(pth[pos + 1], dis[1][b] - pth[pos + 1])) ++pos; centd = pth[pos]; //cerr << centd << "\n"; bool m = Check(n); if(!m) ans *= -1; return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...