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
#include <bits/stdc++.h>
using namespace std;

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

//template <typename T> ostream& operator<<(ostream& out, const vector<T>& xs) {
//	out << "[ ";
//	for (auto&& x : xs)
//		out << x << ' ';
//	return out << ']';
//}

struct HoleEntry {
	long long width;
	int depth;
	static bool compByWidest(HoleEntry a, HoleEntry b) {
		return a.width > b.width;
	}
//	friend ostream& operator<<(ostream& out, HoleEntry he) {
//		return out << "Hole wide " << he.width << " down " << he.depth;
//	}
};
vector<HoleEntry> collectHoleEntries() {
	auto n = PipeHeight();
	auto last = 1000000000000000005ll;
	auto result = vector<HoleEntry>();
	for (int i=0; i<n; ++i) {
		auto curr = HoleDiameter(i+1);
//		if (MyNodeId() == 0) clog << "[" << MyNodeId() << "] " << i << "th hole diameter is " << curr << endl;
		if (curr < last)
			result.push_back(HoleEntry{ curr, i }), last = curr;
	}
	result.push_back(HoleEntry{ 0, n });
	return result;
}

// depth - position of the LAST PLACED block

vector<long long> collectTouchDepths(int from, int to, const vector<HoleEntry>& falls) {
	// [from, to)
	vector<long long> touches;
	for (int iDisc=from; iDisc<to; ++iDisc) {
		auto pos = upper_bound(falls.begin(), falls.end(), HoleEntry{ DiscDiameter(iDisc+1), -1 }, &HoleEntry::compByWidest);
		auto touchDepth = pos->depth;
		touches.push_back(touchDepth);
	}
//	clog << "falls: " << falls << ", touches: " << touches << endl;
	return touches;
}

long long getPriorDepth() {
	if (MyNodeId() == 0)
		return 1000000000000000000ll;
	auto prevId = MyNodeId() - 1;
	Receive(prevId);
	auto priorDepth = GetLL(prevId);
//	clog << "[" << MyNodeId() << "] received " << priorDepth << endl;
	return priorDepth;
}
void sendNewDepth(long long newDepth) {
	if (MyNodeId() == NumberOfNodes() - 1)
		return static_cast<void>(cout << (newDepth+1) << '\n');
	auto nextId = MyNodeId() + 1;
//	clog << "[" << MyNodeId() << "] sent " << newDepth << endl;
	PutLL(nextId, newDepth);
	Send(nextId);
}

long long simulatePart(long long depth, const vector<long long>& touchDepths) {
	for (auto touch : touchDepths) {
//		clog << "simulatePart under " << touch << " from " << depth << " to ";
		depth = min(depth - 1, touch - 1);
//		clog << depth << endl;
	}
	return depth;
}

int main() {
	auto falls = collectHoleEntries();
	auto discFrom = static_cast<long long>(NumberOfDiscs()) * MyNodeId() / NumberOfNodes();
	auto discTo = static_cast<long long>(NumberOfDiscs()) * (MyNodeId() + 1) / NumberOfNodes();
//	clog << "[" << MyNodeId() << "]" << " processing [" << discFrom << ", " << discTo << ")" << endl;
	auto touchDepths = collectTouchDepths(discFrom, discTo, falls);
	auto priorDepth = getPriorDepth();
	auto newDepth = simulatePart(priorDepth, touchDepths);
	sendNewDepth(newDepth);
}