Submission #796647

#	Time	Username	Problem	Language	Result	Execution time	Memory
796647		prvocislo	Towns (IOI15_towns)	C++17	35 / 100	13 ms	888 KiB

towns

#include "towns.h"
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

int getDistance(int i, int j);
int hubDistance(int N, int sub)
{
	int d = 0, a = 0, b = 0;
	for (int i = 0; i < N; i++) if (i != 0)
	{
		int di = getDistance(0, i);
		if (di > d) d = di, a = i;
	}
	vector<int> da(N, 0);
	for (int i = 0; i < N; i++) if (i != a)
	{
		da[i] = getDistance(a, i);
		if (da[i] > d) d = da[i], b = i;
	}
	// lets gooo, a -- b je diagonala
	vector<int> db(N, 0);
	for (int i = 0; i < N; i++) if (i != b)
	{
		db[i] = getDistance(b, i);
	}
	int D = da[b], r = D;
	vector<pair<int, int> > v;
	for (int i = 0; i < N; i++) if (i != a && i != b)
	{
		int c = (da[i] + db[i] - D) / 2;
		v.push_back({ da[i] - c, c });
	}
	sort(v.begin(), v.end());

	vector<int> pf(v.size());
	for (int i = 0; i < v.size(); i++)
	{
		pf[i] = max(v[i].first, v[i].second);
		if (i) pf[i] = max(pf[i], pf[i - 1] + v[i].first - v[i - 1].first);
	}
	vector<int> sf(v.size());
	for (int i = v.size() - 1; i >= 0; i--)
	{
		sf[i] = max(D - v[i].first, v[i].second);
		if (i + 1 < v.size()) sf[i] = max(sf[i], sf[i + 1] + v[i + 1].first - v[i].first);
	}
	for (int i = 0; i < v.size(); i++)
	{
		r = min(r, max(pf[i], sf[i]));
	}
	if (sub <= 2 || sub == 4)
	{
		for (int i = 0; i < v.size(); i++) if (max(pf[i], sf[i]) == r)
		{
			int x = v[i].first;
			int lef = 1 + (lower_bound(v.begin(), v.end(), make_pair(x, 0)) - v.begin());
			int rig = 1 + (v.end() - lower_bound(v.begin(), v.end(), make_pair(x + 1, 0)));
			int mid = N - lef - rig;
			if (max({ lef, rig, mid }) <= N / 2) return r;
		}
		return -r;
	}
	for (int i = 0; i < v.size(); i++) if (max(pf[i], sf[i]) == r)
	{
		int x = v[i].first;
		int lef = 1 + (lower_bound(v.begin(), v.end(), make_pair(x, 0)) - v.begin());
		int rig = 1 + (v.end() - lower_bound(v.begin(), v.end(), make_pair(x + 1, 0)));
		if (max(lef, rig) > N / 2) continue;
		map<int, int> m;
		for (int j = 0; j < N; j++) if (j != a && j != b)
		{
			int c = (da[j] + db[j] - D) / 2;
			if (x == da[j] - c)
			{
				bool found = false;
				for (pair<int, int> p : m)
				{
					int pdi = (da[p.first] + db[p.first] - D) / 2;
					int jdi = (da[j] + db[j] - D) / 2;
					if (pdi + jdi > getDistance(p.first, j))
					{
						found = true;
						m[p.first]++;
						break;
					}
				}
				if (!found) m[j]++;
			}
		}
		bool okay = true;
		for (pair<int, int> p : m) if (p.second > N / 2) okay = false;
		if (okay) return r;
	}
	return -r;
}

Compilation message (stderr)

towns.cpp: In function 'int hubDistance(int, int)':
towns.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
towns.cpp:50:24: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   50 |  for (int i = v.size() - 1; i >= 0; i--)
      |               ~~~~~~~~~^~~
towns.cpp:53:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   if (i + 1 < v.size()) sf[i] = max(sf[i], sf[i + 1] + v[i + 1].first - v[i].first);
      |       ~~~~~~^~~~~~~~~~
towns.cpp:55:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  for (int i = 0; i < v.size(); i++)
      |                  ~~^~~~~~~~~~
towns.cpp:61:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for (int i = 0; i < v.size(); i++) if (max(pf[i], sf[i]) == r)
      |                   ~~^~~~~~~~~~
towns.cpp:64:16: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   64 |    int lef = 1 + (lower_bound(v.begin(), v.end(), make_pair(x, 0)) - v.begin());
      |              ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towns.cpp:65:16: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   65 |    int rig = 1 + (v.end() - lower_bound(v.begin(), v.end(), make_pair(x + 1, 0)));
      |              ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towns.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |  for (int i = 0; i < v.size(); i++) if (max(pf[i], sf[i]) == r)
      |                  ~~^~~~~~~~~~
towns.cpp:74:15: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   74 |   int lef = 1 + (lower_bound(v.begin(), v.end(), make_pair(x, 0)) - v.begin());
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
towns.cpp:75:15: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   75 |   int rig = 1 + (v.end() - lower_bound(v.begin(), v.end(), make_pair(x + 1, 0)));
      |             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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