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
#include <cstdio>
#include <stack>
#include <climits>
#include <cstdlib>
#include <vector>
#include "message.h"
#include "krazki.h"

const int nodeSize = 2000000;

long long v[nodeSize + 7];
int mTeren = 0;

long long policz(int N, long long lastRadius) {
	for (int i = mTeren; i <= mTeren + nodeSize && i <= N; i++) {
		long long ter = HoleDiameter(i);
		lastRadius = std::min(ter, lastRadius);
		v[i - mTeren] = lastRadius;
	}
	return lastRadius;
}

std::pair<int, int> znajdz(int pocz, int M, int mPos) {
	for (int i = pocz; i <= M; i++) {
		long long w = DiscDiameter(i);
		while (mPos > mTeren && v[mPos - mTeren] < w)
			mPos--;
		if (mPos == mTeren)
			return std::make_pair(i, mPos);
		if (i == M)
			return std::make_pair(i, mPos);
		mPos--;
	}
	return std::make_pair(M, 0);
}

int main() {
	int pocz = 1;
	int N = PipeHeight();
	int M = NumberOfDiscs();
	mTeren = nodeSize * MyNodeId() + 1;
	if (mTeren > N)
		return 0;
	long long lastRadius = LLONG_MAX;
	if (MyNodeId() != 0) {
		Receive(MyNodeId() - 1);
		lastRadius = GetLL(MyNodeId() - 1);
	}
	long long r = policz(N, lastRadius);
	if (mTeren+nodeSize < N) {
		PutLL(MyNodeId()+1, r);
		Send(MyNodeId()+1);
	}
	pocz = 1;
	int lastMPos = N;
	if (mTeren+nodeSize < N) {
		Receive(MyNodeId() + 1);
		pocz = GetInt(MyNodeId() + 1);
		lastMPos = GetInt(MyNodeId() + 1);
		if (pocz > M) {
			if (MyNodeId() != 0) {
				PutInt(MyNodeId() - 1, M + 1);
				PutInt(MyNodeId() - 1, lastMPos);
				Send(MyNodeId() - 1);
			}
			return 0;
		}
	}
	std::pair<int, int> s = znajdz(pocz, M, lastMPos);
	if (s.first != M) {
		if (MyNodeId() != 0) {
			PutInt(MyNodeId() - 1, s.first);
			PutInt(MyNodeId() - 1, s.second);
			Send(MyNodeId() - 1);
		} else
			printf("0");
	} else {
		if (MyNodeId() != 0) {
			PutInt(MyNodeId() - 1, M + 1);
			PutInt(MyNodeId() - 1, s.second);
			Send(MyNodeId() - 1);
		}
		printf("%d", s.second);
	}
	return 0;
}