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
#include "message.h"
#include "krazki.h"
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define foreach(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define scanf(...) scanf(__VA_ARGS__)?:0
#define e1 first
#define e2 second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1000000009;
const ll infll=1e18+41;
int id,nodes,n,m,len,pocz[105],kon[105];
ll rurka[105],krazek[105];
pli s[2540000];
pii req[11000];
int main()
{
	id=MyNodeId();
	nodes=NumberOfNodes()-1;
	n=PipeHeight();
	m=NumberOfDiscs();
	len=(max(n+1,m)-1)/nodes+1;
	FOR(i,1,100) pocz[i]=1+len*(i-1),kon[i]=len*i;
	if (id==0)
	{
		int ans=n,ireq=0;
		FOR(i,1,nodes) Receive(i),rurka[i]=GetLL(i),krazek[i]=GetLL(i);
		FOR(j,1,nodes)
		{
			int mozna=3;
			FOR(i,1,nodes)
			{
				if (rurka[i]<krazek[j])
				{
					req[ireq++]=mp(i,j);
					if (mozna==3) mozna=2;
				}
				if (mozna<3) mozna--;
				if (mozna==0) break;
			}
		}
		REP(i,ireq)
		{
			int numer=i%nodes+1;
			PutInt(numer,req[i].e1);
			PutInt(numer,req[i].e2);
			Send(numer);
		}
		REP(i,ireq)
		{
			int numer=i%nodes+1;
			Receive(numer);
			ans=min(ans,GetInt(numer));
		}
		FOR(i,1,nodes) PutInt(i,-1),Send(i);
		printf("%d",ans);
	}
	else
	{
		ll minrurka=infll,maxkrazek=-1;
		if (pocz[id]<=n+1 && kon[id]>n) minrurka=0;
		else FOR(i,pocz[id],min(n+1,kon[id])) minrurka=min(minrurka,HoleDiameter(i));
		FOR(i,pocz[id],min(m,kon[id])) maxkrazek=max(maxkrazek,DiscDiameter(i));
		PutLL(0,minrurka);
		PutLL(0,maxkrazek);
		Send(0);
		while (true)
		{
			Receive(0);
			int prurka=GetInt(0);
			if (prurka==-1) break;
			int pkrazek=GetInt(0);
			int d=min(n+1,kon[prurka])-pocz[prurka]+1;
			FOR(i,pocz[prurka],min(n+1,kon[prurka]))
			{
				if (i<=n) s[i-pocz[prurka]].e1=HoleDiameter(i);
				else s[i-pocz[prurka]].e1=0;
				s[i-pocz[prurka]].e2=i;
			}
			sort(s,s+d);
			FOR(i,1,d-1) s[i].e2=min(s[i].e2,s[i-1].e2);
			int ans=inf;
			FOR(i,pocz[pkrazek],min(m,kon[pkrazek]))
			{
				int ct=lower_bound(s,s+d,mp(DiscDiameter(i),0))-s;
				if (ct==0) continue;
				int poziom=s[ct-1].e2-m+i-1;
				if (poziom<ans) ans=poziom;
			}
			if (ans<0) ans=0;
			PutInt(0,ans);
			Send(0);
		}
	}
}