Submission #556824

#	Time	Username	Problem	Language	Result	Execution time	Memory
556824		blue	Towns (IOI15_towns)	C++17	Compilation error	0 ms	0 KiB

towns

#include "towns.h"
#include <vector>
#include <cmath>
#include <set>
#include <iostream>
#include <cassert>
using namespace std;

namespace
{
	using vi = vector<int>;
	#define sz(x) int(x.size())



	int ST, best_coord;
	vi xcoord;
	int S;
	int T;
	vi distS, dist0;
	int qrc;

}



int best_dist(int i)
{
	int height = (distS[i] + dist0[i] - distS[0])/2;

	return height + abs(xcoord[i] - best_coord);
}

int areequal(int i, int j)
{
	return getDistance(i, j) != best_dist(i) + best_dist(j);

}


int hubDistance(int N, int sub) 
{
	qrc = 0;
	dist0 = vi(N);
	dist0[0] = 0;
	for(int i = 1; i < N; i++)
		dist0[i] = getDistance(0, i);

	S = 0;
	for(int i = 1; i < N; i++)
		if(dist0[i] > dist0[S])
			S = i;

	ST = 0; //diameter

	// cerr << "done\n";

	distS = vi(N);
	distS[S] = 0;
	distS[0] = dist0[S];

	T = 0;
	ST = distS[0];

	for(int i = 1; i < N; i++)
	{
		if(i != S)
		{
			distS[i] = getDistance(S, i);

			if(distS[i] > ST)
			{
				ST = distS[i];
				T = i;
			}
		}
	}

	// cerr << "S = " << S << "\n";


	vi S0_dist(N);
	for(int i = 0; i < N; i++)
		S0_dist[i] = (distS[i] + dist0[i] - distS[0])/2;

	xcoord = vi(N);
	for(int i = 0; i < N; i++)
		xcoord[i] = distS[i] - S0_dist[i];


	int dist0_ST = (dist0[S] + dist0[T] - ST)/2;

	int ST_0coord = dist0[S] - dist0_ST;

	assert(2*ST_0coord >= distS[T]);


	// assert((dist0[S] + getDistance(0, T) - distS[T]) <= distS[T])

	int res = 5'000'000;
	set<int> best_coords;


	for(int i = 0; i < N; i++)
	{
		if(xcoord[i] > ST_0coord) 
			continue;

		int curr = max(xcoord[i], ST - xcoord[i]);

		if(curr < res)
		{
			res = curr;
			best_coords.clear();
		}

		if(curr == res)
		{
			best_coords.insert(xcoord[i]);
		}

	}


	if(sz(best_coords) == 1)
	{
		best_coord = *best_coords.begin();
	}
	else
	{
		int leftcount = 0;
		for(int i = 0; i < N; i++)
		{
			if(xcoord[i] <= *best_coords.begin())
				leftcount++;
		}

		if(2*leftcount >= N)
			best_coord = *best_coords.begin();
		else 
			best_coord = *best_coords.rbegin();
	}

	if(sub <= 2)
		return -res;

	bool balanced = 1;



	if(sub == 4)
	{
		vi ct(3, 0);

		for(int i = 0; i < N; i++)
		{
			if(xcoord[i] < best_coord)
				ct[0]++;
			else if(xcoord[i] > best_coord)
				ct[1]++;
			else 
				ct[2]++;
			balanced = 2*max({ct[0], ct[1], ct[2]}) <= N;
		}
	}
	else
	{
		int candidate = -1;
		int counter = 0;

		for(int i = 0; i < N; i++)
		{
			if(counter == 0)
			{
				candidate = i;
				counter = 1;
			}
			else
			{
				if(areequal(i, candidate))
				{
					counter++;
				}
				else
				{
					counter--;
				}
			}
		}

		int ct = 0;

		for(int i = 0; i < N; i++)
			ct += areequal(i, candidate);

		balanced = (2*ct <= N);
	}

	


	int R = res;

	if(balanced)
		return R;
	else
		return -R;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:163:42: error: no matching function for call to 'max(<brace-enclosed initializer list>)'
  163 |    balanced = 2*max({ct[0], ct[1], ct[2]}) <= N;
      |                                          ^
In file included from /usr/include/c++/10/vector:60,
                 from towns.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
towns.cpp:163:42: note:   candidate expects 2 arguments, 1 provided
  163 |    balanced = 2*max({ct[0], ct[1], ct[2]}) <= N;
      |                                          ^
In file included from /usr/include/c++/10/vector:60,
                 from towns.cpp:2:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
towns.cpp:163:42: note:   candidate expects 3 arguments, 1 provided
  163 |    balanced = 2*max({ct[0], ct[1], ct[2]}) <= N;
      |                                          ^