1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
#include <algorithm>
#include <cstdio>
#include <vector>

#include "message.h"
#include "krazki.h"
#define ODPOWIADAJACY 0

int binsearch_po_wyniku(const std::vector<long long> &tbl, long long srednicaKrazka)
{
	int a = -1;
	int z = tbl.size();

	while (a+1 != z)
	{
		int s = (a+z)/2;
		long long szerokoscDziury = HoleDiameter(tbl[s]);

		if (szerokoscDziury < srednicaKrazka)
		{
			a = s;
		}
		else if (srednicaKrazka <= szerokoscDziury)
		{
			z = s;
		}
	}

	return ((a==-1)? -1: a);
}

struct {
	bool operator () (const int a, const int b) const
	{
		if (HoleDiameter(a) < HoleDiameter(a))
		{
			return true;
		}
		else if (a < b)
		{
			return true;
		}
	}
}porownanieDziur;

int main()
{
	int ja = MyNodeId();
	int uruchomien = NumberOfNodes();
	int glebokosc_rury = PipeHeight();
	int krazkow = NumberOfDiscs();

	int od = 1 + ja * (glebokosc_rury/uruchomien) + std::min(ja, glebokosc_rury%uruchomien);
	int po = od + (glebokosc_rury/uruchomien) - 1 + ((ja+1) <= glebokosc_rury%uruchomien);

	int najzawczesniej = 0;

	if (od <= po)
	{
		std::vector<long long> dziury(std::max(0,po-od+1));

	//	fprintf(stderr, "%d-%d\n", od, po);

		for(int i=0; i <= od-po; ++i)
		{
			dziury[i] = od+i;
		}

		std::sort(dziury.begin(), dziury.end(), porownanieDziur);

		for (int i=1;i<=krazkow;++i)
		{
			int znajda = binsearch_po_wyniku(dziury, DiscDiameter(i));

			if (znajda == -1)
			{
				continue;
			}

			int zawczesnie = (glebokosc_rury-i+1) - (dziury[znajda] - 1);

			if (najzawczesniej < zawczesnie)
			{
				najzawczesniej = zawczesnie;
			}
		}
	}

	if (ja != ODPOWIADAJACY)
	{
		PutInt(ODPOWIADAJACY, najzawczesniej);
		Send(ODPOWIADAJACY);
//		fprintf(stderr, "%d\n", najzawczesniej);
	}
	else
	{
//		fprintf(stderr, "%d\n", najzawczesniej);
		for (int i=1; i < uruchomien; ++i)
		{
			int nadawca = Receive(-1);
			int zawczesnie = GetInt(nadawca);

			if (najzawczesniej < zawczesnie)
			{
				najzawczesniej = zawczesnie;
			}
		}

		printf("%d\n", std::max(0, ((glebokosc_rury-krazkow+1) - najzawczesniej)));
	}
}