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
#include <bits/stdc++.h>
#include "krazki.h"
#include "message.h"
using namespace std;
using ll=long long;
const ll INF=2e18;
ll n, m;
inline ll MyHoleDiameter(int i) //zle przeczytalem tresc :P
{
	return HoleDiameter(n-i+1);
}
int result(int pipe_l, int pipe_r, int disc_l, int disc_r)
{
	if(pipe_r==pipe_l||disc_r==disc_l) return 0;
	vector<ll> discs(disc_r-disc_l), holes(pipe_r-pipe_l);
	for(int i=0; i<disc_r-disc_l; ++i) discs[i]=DiscDiameter(i+1+disc_l);
	for(int i=0; i<pipe_r-pipe_l; ++i) holes[i]=MyHoleDiameter(i+1+pipe_l);
	for(int i=1; i<disc_l-disc_r; ++i) discs[i]=max(discs[i], discs[i-1]);
	for(int i=pipe_r-pipe_l-2; i>=0; --i) holes[i]=min(holes[i], holes[i+1]);
	int j=0, res=0;
	for(int i=0; i<discs.size(); ++i)
	{
		while(j<holes.size()&&holes[j]<discs[i]) ++j;
		if(j>0) res=max(res, pipe_l-disc_l+j-i);
	}
	/*
	if(res>0)
	{
		printf("Instance %d here!\n", MyNodeId());
		if(1)
		{
			printf("[%d, %d), [%d, %d)\n", pipe_l, pipe_r, disc_l, disc_r);
			printf("Content:\n");
			for(ll i: holes) printf("%lld ", i);
			printf("\n");
			for(ll i: discs) printf("%lld ", i);
			printf("\n");
		}
	}
	*/	
	return res;
}	
int main()
{
	n=PipeHeight(), m=NumberOfDiscs();
	//if(MyNodeId()==0) printf("Hello World!\n");
	int nodes=NumberOfNodes(), id=MyNodeId();
	nodes=min(nodes, (int)min(n, m));
	if(id>=nodes) return 0; //jestes bezuzyteczna
	ll pipe_mn=INF, disc_mx=0;
	for(int i=id*n/nodes+1; i<(id+1)*n/nodes+1; ++i) pipe_mn=min(pipe_mn, MyHoleDiameter(i));
	for(int i=id*m/nodes+1; i<(id+1)*m/nodes+1; ++i) disc_mx=max(disc_mx, DiscDiameter(i));
	PutLL(0, pipe_mn);
	PutLL(0, disc_mx);
	Send(0);
	if(id==0)
	{
		vector<ll> holes(nodes), discs(nodes);
		for(int i=0; i<nodes; ++i)
		{
			Receive(i);
			holes[i]=GetLL(i);
			discs[i]=GetLL(i);
		}
		for(int i=1; i<nodes; ++i) discs[i]=max(discs[i], discs[i-1]);
		for(int i=nodes-2; i>=0; --i) holes[i]=min(holes[i], holes[i+1]); 
		/*
		for(ll i: holes) printf("%lld ", i);
		printf("\n");
		for(ll i: discs) printf("%lld ", i);
		printf("\n");
		*/
		int i1=0, i2=0;
		while(i1<nodes&&i2<nodes)
		{
			PutInt((i1+i2)/2, i1);
			PutInt((i1+i2)/2, i2);
			if(i2==nodes-1||(i1<nodes-1&&holes[i1+1]<discs[i2+1])) ++i1;
			else ++i2;
		}
		for(int i=0; i<nodes; ++i) Send(i);
	}
	Receive(0);
	int mx=0;
	for(int whatever=0; whatever<2; ++whatever)
	{
		int i1=GetInt(0);
		int i2=GetInt(0);
		mx=max(mx, result(i1*n/nodes, (i1+1)*n/nodes, i2*m/nodes, (i2+1)*m/nodes));
		if(id==nodes-1) break;
	}
	PutInt(0, mx);
	Send(0);
	if(id==0)
	{
		for(int i=0; i<nodes; ++i)
		{
			Receive(i);
			mx=max(mx, GetInt(i));
		}
		int res=max(n-m-mx+1, 0LL);
		printf("%d\n", res);
	}	
}