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
#include <cstdio>
#include <cstdlib>
#include "message.h"
#include "krazki.h"
//#include "krazki.cpp"

int BS(long long int tabl[],int pocz,int kon,long long int wart)
{
	int tmp;
	if (tabl[pocz]<wart) return 0;
	while (pocz+1<kon)
	{
		tmp=(pocz+kon)/2;
		if (tabl[tmp]<wart)
			kon=tmp;
		else
			pocz=tmp;
	}
	return pocz;
}

int main()
{
	long long int * min;
	int Nod,ID,pocz,kon;
	int N,m;
	m=NumberOfDiscs();
	N=PipeHeight();
	Nod=NumberOfNodes();
	ID=MyNodeId();
	pocz=m*ID/Nod+1;
	kon=m*(ID+1)/Nod+1;
	min=(long long int *) malloc(sizeof(long long int)*(N+2));
	min[N+1]=0;
	long long int najw;
	int Zajete=N+1,ilewpad=kon-pocz,gdziekon=N,przes,wolne;
	long long int max=2000000000,tmp;
	for (int i=1;i<=N;i++)
	{
		tmp=HoleDiameter(i);
		if (max>tmp) max=tmp;
		min[i]=max;
	}
	if (kon>pocz) gdziekon=BS(min,1,N+1,DiscDiameter(pocz));
	for (int i=pocz;i<kon;i++)
	{
		tmp=DiscDiameter(i);
		Zajete=BS(min,1,Zajete,tmp);
	}
	free(min);
	int Zajete2,ilewpad2,gdziekon2;
	//printf("mam ID %d. analizuje krazki %d - %d. zajety: %d ilewpad: %d gdziekon: %d\n",ID,pocz,kon,Zajete,ilewpad,gdziekon);
	if (ID!=0)
	{
		PutInt(0,Zajete);
		PutInt(0,ilewpad);
		PutInt(0,gdziekon);
		Send(0);
	}
	else
	{
		for (int i=1;i<Nod;i++)
		{
			Receive(i);
			Zajete2=GetInt(i);
			ilewpad2=GetInt(i);
			gdziekon2=GetInt(i);
			
			if (gdziekon2<Zajete)
			{
				Zajete=Zajete2;
			} else
			{
				przes=gdziekon2-Zajete+1;
				wolne=gdziekon2-Zajete2-ilewpad2+1;
				if (wolne>=przes)
					Zajete=Zajete2;
				else
					Zajete=Zajete2-(przes-wolne);
			}
			if (Zajete<1)
			{
				printf("0\n");
				return 0;
			}
		}
		//printf("mam ID %d. analizuje krazki %d - %d. zajety: %d ilewpad: %d gdziekon: %d\n",ID,pocz,kon,Zajete,ilewpad,gdziekon);
		printf("%d\n",Zajete);
	}
	return 0;
}