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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <map>

#include "krazki.h"
#include "message.h"

using namespace std;

#define DIV 17000
#define INF 1000000000000000009LL
#define MXSZ 200000009

long long divminims[MXSZ/DIV+9];
int myid, nodes, ph;

long long diam(int i){
	if(i<0){ return INF; }
	if(i>=ph){ return 0; }
	return HoleDiameter(i+1);
}

vector<long long> mindiam;
int offset=1e9;
long long getMinDiam(int index){
	if(offset>index){
		offset=(index-1)/DIV*DIV-1;
		mindiam.clear();
		mindiam.push_back(divminims[(offset+1)/DIV]);
		for(int i=1;i<=DIV;i++){
			mindiam.push_back( min(mindiam.back(), diam(offset+i)) );
		}
	}
	return mindiam[index-offset];
}

int main() {
	myid=MyNodeId();
	nodes=NumberOfNodes();
	ph=PipeHeight();
	vector<long long>minims;
	for(int i=myid; ;i+=nodes){
		int from=i*DIV;
		int to=(i+1)*DIV;
		if(to>ph){ to=ph; }
		if(from>=ph){ break; }
		long long mn=INF;
		for(int j=from;j<to;j++){
			long long hd=diam(j);
			if(hd<mn){ mn=hd; }
		}
		minims.push_back(mn);
	}
	for(int i=0;i<nodes;i++){
		PutInt(i, minims.size());
		for(auto x:minims){
			PutLL(i, x);
		}
		Send(i);
	}
	//printf("Sent %zu bytes...\n", minims.size()*8*nodes);
	for(int i=0;i<nodes;i++){
		Receive(i);
		int amount=GetInt(i);
		for(int j=0;j<amount;j++){
			divminims[i+nodes*j+1]=GetLL(i);
		}
	}
	divminims[0]=INF;
	long long minsofar=INF;
	for(int i=0; ;i++){
		if(divminims[i] < minsofar){
			minsofar=divminims[i];
		}
		if(minsofar < divminims[i]){
			divminims[i]=minsofar;
		}
		if( i*DIV>=ph ){ break; }
	}
	int discs=NumberOfDiscs();
	// My node deals with ith partition of discs.
	int from=(long long)myid*discs/nodes;
	int to=(long long)(myid+1)*discs/nodes;
	int firstDisc=0;
	int lastDisc=0;
	int index=ph-1;
	for(int i=from;i<to;i++){
		long long disc=DiscDiameter(i+1);
		while(divminims[index/DIV]<disc){
			index=(index/DIV)*DIV-1;
		}
		if(index==-1){ index--;break; }

		while(getMinDiam(index)<disc){
			index--;
		}
		lastDisc=index;
		if(firstDisc==0){ firstDisc=index; }
		index--;
	}
	index++;
	PutInt(0, to-from);
	PutInt(0, firstDisc);
	PutInt(0, lastDisc);
	Send(0);

	if(myid!=0){ return 0; }

	int hi=ph;
	for(int i=0;i<nodes;i++){
		Receive(i);
		int discs=GetInt(i);
		int first=GetInt(i);
		int last=GetInt(i);
		if(discs==0){ continue; }
		// Compressing values.
		// [=====] last
		// -       gap
		// -[==]   other
		// -[====] first
		// -
		// -[====] hi (previous)
		int gap=first-last-discs+1;
		if(hi>first){ hi=last; continue; }
		// Otherwise, we need to move some discs up.
		int amount=first-hi+1;
		if(amount<=gap){ hi=last; continue; }
		// Otherwise, we need to move even the top disc up.
		int left=amount-gap;
		hi=last-left;
	}
	if(hi<0){ hi=-1; }
	printf("%d\n", hi+1);


}