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
#include <algorithm>
#include <climits>
#include <functional>
#include <iostream>
#include <vector>
#include "krazki.h"
#include "message.h"

int main() {
	int prevNodeId = MyNodeId() - 1, nextNodeId = MyNodeId() + 1;
	int top = MyNodeId() * (long long)PipeHeight() / NumberOfNodes();
	int bottom = nextNodeId * (long long)PipeHeight() / NumberOfNodes();
	int first = MyNodeId() * (long long)NumberOfDiscs() / NumberOfNodes();
	int last = nextNodeId * (long long)NumberOfDiscs() / NumberOfNodes();
	std::vector<long long> pipeDiameter(bottom - top);
	int segment = top;
	long long narrowest = LLONG_MAX;
	for (auto&& diameter : pipeDiameter) {
		diameter = narrowest = std::min(narrowest, HoleDiameter(++segment));
	}
	int disc = first;
	long long widest = 0;
	for (int i = first; i < last; i++) {
		widest = std::max(widest, DiscDiameter(++disc));
	}
	long long narrowestAbove;
	if (MyNodeId()) {
		Receive(prevNodeId);
		narrowest = std::min(narrowest, narrowestAbove = GetLL(prevNodeId));
		widest = std::max(widest, GetLL(prevNodeId));
	} else {
		narrowestAbove = LLONG_MAX;
	}
	if (nextNodeId != NumberOfNodes()) {
		PutLL(nextNodeId, narrowest);
		PutLL(nextNodeId, widest);
		Send(nextNodeId);
	}
	if (MyNodeId()) {
		PutLL(0, narrowest);
		PutLL(0, widest);
		Send(0);
	}
	auto it = std::lower_bound(pipeDiameter.begin(), pipeDiameter.end(), narrowestAbove, std::greater<long long>());
	std::fill(pipeDiameter.begin(), it, narrowestAbove);
	int discNodeId = 0;
	if (MyNodeId() == 0) {
		std::vector<long long> narrowestIn(NumberOfNodes()), widestIn(NumberOfNodes());
		narrowestIn[MyNodeId()] = narrowest;
		widestIn[MyNodeId()] = widest;
		for (int i = 1; i < NumberOfNodes(); i++) {
			int id = Receive(-1);
			narrowestIn[id] = GetLL(id);
			widestIn[id] = GetLL(id);
		}
		int j = 0;
		for (int i = NumberOfNodes(); i--;) {
			while (j < NumberOfNodes() && widestIn[j] <= narrowestIn[i]) {
				j++;
			}
			if (i) {
				PutInt(i, j);
				Send(i);
			} else {
				discNodeId = j;
			}
		}
	} else {
		Receive(0);
		discNodeId = GetInt(0);
	}
	int result = PipeHeight() - NumberOfDiscs() + 1;
	if (result >= 0 && discNodeId != NumberOfNodes()) {
		int disc = discNodeId * (long long)NumberOfDiscs() / NumberOfNodes();
		bool remainingDiscs = true;
		while (disc < PipeHeight() - bottom && DiscDiameter(disc + 1) <= narrowest) {
			if (++disc == NumberOfDiscs()) {
				remainingDiscs = false;
				break;
			}
		}
		if (remainingDiscs) {
			for (int i = bottom; i-- > top;) {
				if (pipeDiameter[i - top] >= DiscDiameter(disc + 1)) {
					if (++disc == NumberOfDiscs()) {
						remainingDiscs = false;
						result = i + 1;
						break;
					}
				}
			}
		}
		if (remainingDiscs)
			result = disc + top + 1 - NumberOfDiscs();
	}
	if (MyNodeId() == 0) {
		for (int i = 1; i < NumberOfNodes(); i++) {
			int id = Receive(-1);
			result = std::min(GetInt(id), result);
		}
		std::cout << (result < 0 ? 0 : result) << '\n';
	} else {
		PutInt(0, result);
		Send(0);
	}
	return 0;
}