Submission #52129

#	Time	Username	Problem	Language	Result	Execution time	Memory
52129		spencercompton	Towns (IOI15_towns)	C++17	61 / 100	28 ms	676 KiB

towns

#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 (stderr)

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();
                     ^

• Subtask 1: 13 / 13
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 0 / 39