| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 133754 | MAMBA | Towns (IOI15_towns) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i , j , k) for (int i = j; i < k; i++)
typedef long long ll;
template<class S, class T>
inline bool smax(S &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
const int MAXN = 1e3;
ll D1[MAXN], D2[MAXN], f[MAXN], z[MAXN];
int hubDistance(int N, int sub) {
int r1 = 0;
ll d = 0;
rep(i , 1 , N)
if (smax(d , getDistance(0 , i)))
r1 = i;
rep(i , 0 , N)
D1[i] = getDistance(r1 , i);
int r2 = max_element(D1 , D1 + N) - D1;
rep(i , 0 , N)
D2[i] = getDistance(r2 , i);
ll limit = D1[r2];
rep(i , 0 , N)
f[i] = (limit + D1[i] - D2[i]) / 2;
sort(f , f + N);
ll R = limit;
rep(i , 0 , N)
R = min(R , max(f[i] , limit - f[i]));
if (sub <= 2) return R;
// DONE DONE DONE DONE DONE
int i1 = 0, i2 = 0;
int j1 = 0, j2 = 0;
rep(i , 0 , N) {
if (f[i] == R) i2++;
if (f[i] == limit - R) i1++;
if (f[i] < limit - R) j1++;
if (f[i] > R) j2++;
}
int n2 = N / 2;
if (sub == 4) {
if (j1 <= n2 && i1 <= n2 && (N - j1 - i1) <= n2)
return R;
if (j2 <= n2 && i2 <= n2 && (N - j2 - i2) <= n2)
return R;
return -R;
}
// DONE DONE DONE DONE DONE DONE DONE DONE
rep(i , 0 , N) {
z[i] = (limit + D1[i] - D2[i]) / 2;
f[i] = D1[i] - z[i];
}
auto check = [](ll g, int n2) -> bool {
int cnt = 0;
int last = -1;
rep(i , 0 , N)
if (z[i] == g) {
if (last == -1 || getDistance(i , last) == f[i] + f[last]) {
cnt--;
if (cnt <= 0) {
cnt = 1;
last = i;
}
}
else
cnt++;
}
cnt = 0;
rep(i , 0 , N)
if (z[i] == g && getDistance(last , i) != f[i] + f[last])
cnt++;
return cnt <= n2;
};
if (limit == 2*R) {
if (j1 <= n2 && j2 <= n2)
if (check(R , n2))
return R;
return -R;
}
if (j2 + i2 <= n2) {
if (check(limit - R , n2))
return R;
}
if (i1 + j1 <= n2) {
if (check(R , n2))
return R;
}
return -R;
}