#include "towns.h"
#include <bits/stdc++.h>
using namespace std;
// int getDistance(int a, int b){
// cout << "? " << a << " " << b << endl;
// int x;
// cin >> x;
// return x;
// }
int hubDistance(int N, int sub) {
pair<int, int > best = make_pair(-1,-1);
//first is dist, second is ind
for(int i = 1; i<N; i++){
pair<int, int> now = make_pair(getDistance(0,i),i);
best = max(best,now);
}
int first = best.second;
best = make_pair(-1,-1);
int A[N];
int B[N];
for(int i = 0; i<N; i++){
if(i==first){
continue;
}
pair<int, int> now = make_pair(getDistance(first,i),i);
A[i] = now.first;
best = max(best,now);
}
int second = best.second;
int diameter = A[second];
int inf = 100000000;
int ans = inf;
vector<vector<int> > li;
int point = 0;
int most = N/2;
bool balanced = false;
map<pair<int, int>, int> m;
vector<int> ali;
int x[N];
vector<pair<int, int> > pars;
for(int i = 0; i<N; i++){
if(i==first || i==second){
continue;
}
B[i] = getDistance(i,second);
x[i] = (A[i]+B[i]-diameter)/2;
int a = A[i]-x[i];
int b = B[i]-x[i];
pair<int, int> comb = make_pair(a,b);
bool newer = false;
if(m.find(comb)==m.end()){
newer = true;
m[comb] = point++;
vector<int> xx;
li.push_back(xx);
pars.push_back(make_pair(a,point-1));
}
li[m[comb]].push_back(i);
if(max(a,b)<ans){
ans = max(a,b);
ali.clear();
ali.push_back(point-1);
}
else if(max(a,b)==ans && newer){
ali.push_back(point-1);
}
}
if(sub<=2){
return ans;
}
sort(pars.begin(),pars.end());
int tot = N;
int bef = 1;
for(int z = 0; z<pars.size(); z++){
int i = pars[z].second;
if(bef>most || (tot-bef-li[i].size())>most){
bef += li[i].size();
continue;
}
bool ishub = false;
for(int j = 0; j<ali.size(); j++){
ishub |= ali[j]==i;
}
if(!ishub){
bef += li[i].size();
continue;
}
if(li[i].size()>most){
if(sub==4){
bef += li[i].size();
continue;
}
int cur = li[i][0];
int score = 1;
for(int j = 1; j<li[i].size(); j++){
// cout << "# " << score << " " << cur << endl;
if(score==0){
cur = li[i][j];
score = 1;
}
else if(getDistance(li[i][j],cur)==x[li[i][j]]+x[cur]){
// cout << "A " << endl;
score--;
}
else{
// cout << "B " << endl;
score++;
}
}
if(score==0){
balanced = true;
break;
}
int cnt = 1;
for(int j = 0; j<li[i].size(); j++){
if(li[i][j]==cur){
bef += li[i].size();
continue;
}
if(getDistance(li[i][j],cur)<x[li[i][j]]+x[cur]){
cnt++;
}
}
if(cnt <= most){
balanced = true;
}
}
else{
balanced = true;
break;
}
bef += li[i].size();
}
if(!balanced){
ans = -ans;
}
return ans;
}
// int main(){
// cout << "DONE " << hubDistance(6,3) << endl;
// }
Compilation message
towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int z = 0; z<pars.size(); z++){
~^~~~~~~~~~~~
towns.cpp:77:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(bef>most || (tot-bef-li[i].size())>most){
~~~~~~~~~~~~~~~~~~~~~~^~~~~
towns.cpp:78:22: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
bef += li[i].size();
^
towns.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<ali.size(); j++){
~^~~~~~~~~~~
towns.cpp:86:22: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
bef += li[i].size();
^
towns.cpp:89:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(li[i].size()>most){
~~~~~~~~~~~~^~~~~
towns.cpp:91:23: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
bef += li[i].size();
^
towns.cpp:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 1; j<li[i].size(); j++){
~^~~~~~~~~~~~~
towns.cpp:116:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j<li[i].size(); j++){
~^~~~~~~~~~~~~
towns.cpp:118:24: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
bef += li[i].size();
^
towns.cpp:133:21: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
bef += li[i].size();
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
376 KB |
Output is correct |
| 2 |
Correct |
25 ms |
428 KB |
Output is correct |
| 3 |
Correct |
2 ms |
428 KB |
Output is correct |
| 4 |
Correct |
23 ms |
504 KB |
Output is correct |
| 5 |
Correct |
22 ms |
504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
504 KB |
Output is correct |
| 2 |
Correct |
17 ms |
504 KB |
Output is correct |
| 3 |
Correct |
23 ms |
504 KB |
Output is correct |
| 4 |
Correct |
26 ms |
652 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
652 KB |
Output is correct |
| 2 |
Correct |
28 ms |
676 KB |
Output is correct |
| 3 |
Correct |
3 ms |
676 KB |
Output is correct |
| 4 |
Correct |
24 ms |
676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
676 KB |
Output is correct |
| 2 |
Correct |
22 ms |
676 KB |
Output is correct |
| 3 |
Correct |
23 ms |
676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
