이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 505;
int x, y;
int D0[Nmax], D1[Nmax], D2[Nmax], Up[Nmax], L[Nmax], R[Nmax];
map< int, vector<int> > gr;
void prepare(int n)
{
int i;
for(i=0; i<n; ++i) D0[i] = getDistance(0, i);
x = max_element(D0, D0+n) - D0;
for(i=0; i<n; ++i) D1[i] = getDistance(x, i);
y = max_element(D1, D1+n) - D1;
for(i=0; i<n; ++i) D2[i] = getDistance(y, i);
}
bool check(vector<int> &v, int n)
{
if(v.size() <= n/2) return 1;
int candidat = v[0];
int cnt = 0;
for(auto it : v)
if(getDistance(candidat, it) == Up[candidat] + Up[it]) /// bucketuri diferite
{
--cnt;
if(!cnt) candidat = it, cnt = 0;
}
else ++cnt;
cnt = 0;
for(auto it : v)
if(getDistance(candidat, it) == Up[candidat] + Up[it]) ++cnt;
return (cnt <= n/2);
}
int hubDistance(int n, int subtask)
{
prepare(n);
int total = D1[y];
int ans = 2e9;
int i;
gr.clear();
for(i=0; i<n; ++i)
{
Up[i] = D1[i] + D2[i] - total;
assert(Up[i] % 2 == 0);
Up[i] /= 2;
L[i] = D1[i] - Up[i];
R[i] = D2[i] - Up[i];
gr[L[i]].push_back(i);
ans = min(ans, max(L[i], R[i]));
}
bool balanced = 0;
int cnt1 = 0, cnt2 = n;
for(auto &it : gr)
{
cnt2 -= it.second.size();
if(max(it.first, total - it.first) == ans && cnt1 <= n/2 && cnt2 <= n/2)
balanced |= check(it.second, n);
cnt1 += it.second.size();
}
return ans * (balanced ? 1 : -1);
}
컴파일 시 표준 에러 (stderr) 메시지
towns.cpp: In function 'void prepare(int)':
towns.cpp:18:31: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
x = max_element(D0, D0+n) - D0;
~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp:22:31: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
y = max_element(D1, D1+n) - D1;
~~~~~~~~~~~~~~~~~~~~~~^~~~
towns.cpp: In function 'bool check(std::vector<int>&, int)':
towns.cpp:30:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(v.size() <= n/2) return 1;
~~~~~~~~~^~~~~~
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:80:32: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
cnt2 -= it.second.size();
^
towns.cpp:85:32: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
cnt1 += it.second.size();
^
towns.cpp:51:28: warning: unused parameter 'subtask' [-Wunused-parameter]
int hubDistance(int n, int subtask)
^~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |