| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 730754 | Vu_CG_Coder | Towns (IOI15_towns) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
int f[110][110];
// int getDistance(int x , int y){
// return f[x][y];
// }
int sub1(int N,int sub){
int n = N;
pair <int,int> tmp;
vector <int> val , value;
val.assign(n,0);
value.assign(n,0);
for (int i = 1 ; i < n ; i++){
int x = getDistance(0,i);
tmp = max(tmp,make_pair(x,i));
}
int u = tmp.second;
tmp.first = 0;
for (int i = 0 ; i < n ; i++)
if (i != u){
int x = getDistance(i,u);
val[i] = x;
tmp = max(tmp,make_pair(x,i));
}
int v = tmp.second;
int R = 1e9;
//cout << u << " " << v << "\n";
for (int i = 0 ; i < n ; i++)
if (i != u && i != v){
int x = getDistance(v,i);
value[i] = x;
int y = val[i];
int z = val[v];
int a = (x + y - z)/2;
int b = x - a;
int c = z - b;
int r = max(a,max(b,c));
if (r < R){
tmp = make_pair(b,c);
R = r;
}
}
if (sub < 3) return R;
// cout << tmp.first << " " << tmp.second << "\n";
int cntu = 1 , cntv = 1 , cnt = 0;
for (int i = 0 ; i < n ; i++)
if (i != u && i != v)
{
int x = val[i];
int y = val[v];
int z = value[i];
int a = (x + y - z)/2;
// cout << i << " " << a << '\n';
if (a < tmp.second) cntu++;
if (a == tmp.second) cnt++;
if (a > tmp.second) cntv++;
}
// cout << cntu << " " << cntv << " " << cnt << "\n";
if (cntu > n/2 || cntv > n/2 || cnt > n/2) return -R;
return R;
}
// int hubDistance(int N, int sub) {
// if (sub < 3 || sub == 4) return sub1(N,sub);
// }
// int main(){
// freopen("txt.inp","r",stdin);
// freopen("txt.out","w",stdout);
// int n;
// cin >> n;
// for (int i = 0 ; i < n ; i++)
// for (int j = 0 ; j < n ; j++)
// cin >> f[i][j];
// cout << hubDistance(n,4);
// return 0;
// }