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
#include <algorithm>
#include <cstdio>
#include <vector>
#include "krazki.h"
#include "message.h"
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

typedef long long LL;
typedef vector<LL> VLL;

const LL INF = 1000000000000000000LL;

int n, m, beg, len, p;
VLL hole;

LL getLast() {
	return !hole.empty() ? hole.back() : INF;
}

bool check() {
	int mi = max(p - 1, beg), ma = min(m + p - 1, beg + len);
	FOR(i,mi,ma) if (DiscDiameter(m - i + p - 1) > hole[i - beg]) return 0;
	return 1;
}

int main() {
	int nodes = NumberOfNodes();
	int me = MyNodeId();
	n = PipeHeight();
	m = NumberOfDiscs();
	if (m > n) {
		if (!me) printf("0\n");
		return 0;
	}
	beg = LL(me) * n / nodes;
	len = LL(me + 1) * n / nodes - beg;
	hole.resize(len);
	REP(i,len) hole[i] = HoleDiameter(i + beg + 1);
	FOR(i,1,len) hole[i] = min(hole[i], hole[i - 1]);
	if (!me) {
		LL prev = getLast();
		FOR(x,1,nodes) {
			PutLL(x, prev);
			Send(x);
			Receive(x);
			prev = min(prev, GetLL(x));
		}
		int good = 0, bad = n - m + 2;
		while (good + 1 < bad) {
			p = (good + bad) >> 1;
			if (nodes > 1) {
				PutInt(1, p);
				Send(1);
			}
			bool ok = check();
			FOR(x,1,nodes) {
				int y = Receive(-1);
				ok &= GetInt(y);
			}
			if (ok) good = p;
			else bad = p;
		}
		FOR(x,1,nodes) {
			PutInt(x, -1);
			Send(x);
		}
		printf("%d\n", good);
	} else {
		PutLL(0, getLast());
		Send(0);
		Receive(0);
		LL fix = GetLL(0);
		REP(i,len)
			if (hole[i] > fix)
				hole[i] = fix;
			else
				break;
		for (;;) {
			int y = Receive(-1);
			p = GetInt(y);
			int t1 = me << 1;
			int t2 = (me << 1) + 1;
			if (t1 < nodes) {
				PutInt(t1, p);
				Send(t1);
			}
			if (t2 < nodes) {
				PutInt(t2, p);
				Send(t2);
			}
			if (p < 0) break;
			PutInt(0, check());
			Send(0);
		}
	}
}