//	Michał Wiatrowski

#include <iostream>
#include <vector>
#include <algorithm>

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

using namespace std;

int main() {
	int TOTAL_NODES = NumberOfNodes();

	int id = MyNodeId();

	int n = PipeHeight();
	int m = NumberOfDiscs();

	int segment_size = (n + TOTAL_NODES - 1) / TOTAL_NODES;
	int segment_b = segment_size * id;
	int segment_e = segment_size * (id + 1);

	int chunk_size = (m + TOTAL_NODES - 1) / TOTAL_NODES;
	int chunk_b = chunk_size * id;
	int chunk_e = chunk_size * (id + 1);

	vector<long long> pipe(segment_size, -1);	
	vector<pair<int, long long>> reach;
	vector<pair<long long, long long>> segments(TOTAL_NODES);

	//	Czytanie danych o swoim wycinku rurki
	{
		for (int i = 0; i < segment_size; ++i) {
			if (segment_b + i >= n)
				break;
			pipe[i] = HoleDiameter(n - (segment_b + i));
		}
	}

	//	Przetwarzanie wycinka rurki
	{
		long long minimum = pipe[segment_size - 1];
		for (int i = segment_size - 1; i >= 0; --i) {
			minimum = std::min(minimum, pipe[i]);
			pipe[i] = minimum;
		}
	}

	//	Propagacja minimów - wysyłanie
	{
		long long minimum = pipe[0];
		for (int i = 0; i < id; ++i) {
			PutLL(i, minimum);
			Send(i);
		}
	}

	//	Propagacja minimów - odbieranie
	{
		long long real_min = pipe[0];

		for (int i = id + 1; i < TOTAL_NODES; ++i) {
			Receive(i);
			real_min = std::min(real_min, GetLL(i));
		}

		for (int i = 0; i < segment_size; ++i)
			pipe[i] = std::min(pipe[i], real_min);
	}

	//	Wysyłanie całkowitego zakresu
	{
		for (int i = 0; i < TOTAL_NODES; ++i) {
			PutLL(i, pipe.front());
			PutLL(i, pipe.back());
			Send(i);
		}
	}

	//	Odbieranie zakresów poszczególnych jednostek
	{
		for (int i = 0; i < TOTAL_NODES; ++i) {
			Receive(i);
			segments[i].first = GetLL(i);
			segments[i].second = GetLL(i);
		}
	}

	//	Zbieranie podpowiedzi
	vector<int> hints(TOTAL_NODES, m);
	{
		vector<int> dest(chunk_size, -1);

		auto search_id = [&](long long r) {
			int low = 0;
			int upp = TOTAL_NODES;

			if (segments[0].second >= r)
				return 0;

			while (upp - low > 1) {
				int mid = (low + upp) / 2;
				
				if (segments[mid].second < r)
					low = mid;
				else
					upp = mid;
			}

			return (upp < TOTAL_NODES) ? upp : (TOTAL_NODES - 1);
		};

		int max = 0;
		for (int i = 0; i < chunk_size; ++i) {
			if (chunk_b + i >= m)
				break;
			int dest_id = search_id(DiscDiameter(m - (chunk_b + i)));
			
			if (dest_id < max)
				dest_id = max;
			else if (max < dest_id)
				max = dest_id;

			if (hints[dest_id] == m)
				hints[dest_id] = chunk_b + i;
		}
	}

	//	Wysyłanie podpowiedzi
	{
		for (int i = 0; i < TOTAL_NODES; ++i) {
			PutLL(i, hints[i]);
			Send(i);
		}
	}

	//	Odbieranie podpowiedzi
	int start_pos = m;
	{
		for (int i = 0; i < TOTAL_NODES; ++i) {
			Receive(i);
			int s = GetInt(i);

			if (s != -1)
				start_pos = std::min(start_pos, s);
		}
	}

	//	Przeglądanie właściwych krążków
	int used_discs;
	int gaps;
	{
		int disc_i = start_pos;
		int missed = 0;
		for (int pipe_pos = chunk_b; pipe_pos < chunk_e; ++pipe_pos) {
			if (pipe_pos >= n)
				break;

			if (disc_i >= m) {
				missed += 1;
				continue;
			}

			long long r = DiscDiameter(m - disc_i);
			long long& d = pipe[pipe_pos - chunk_b];

			if (r > d)
				missed += 1;
			else
				disc_i += 1;
		}

		used_discs = (disc_i - start_pos);
		gaps = missed;
	}

	//	"Przepychanie" krążków
	{
		int start_prev = 0;
		int used_prev = 0;
		if (id != 0) {
			Receive(id - 1);
			start_prev = GetInt(id - 1);
			used_prev = GetInt(id - 1);
		}

		if (start_pos == m) {
			start_pos = start_prev + used_prev;
			used_discs = gaps;
		} else {
			int first_unused = start_prev + used_prev;

			int leftover = start_pos - first_unused;
			start_pos = first_unused;
			used_discs += std::min(leftover, gaps);
		}

		if (id != TOTAL_NODES - 1) {
			PutInt(id + 1, start_pos);
			PutInt(id + 1, used_discs);
			Send(id + 1);
		}
	}

	//	Jeszcze jeden przebieg żeby znaleźć gdzie wylądował
	//	ostatni krążek
	{
		if (start_pos + used_discs == m) {
			int disc_i = start_pos;

			for (int pipe_pos = chunk_b; pipe_pos < chunk_e; ++pipe_pos) {
				if (pipe_pos >= n)
					break;

				long long r = DiscDiameter(m - disc_i);
				long long& d = pipe[pipe_pos - chunk_b];

				if (r <= d) {
					if (disc_i == m-1) {
						//	Wysyłanie komunikatu
						PutInt(0, n - pipe_pos);
						Send(0);
					}
					disc_i += 1;
				}
			}
		}

		if (id == TOTAL_NODES - 1 && start_pos + used_discs < m) {
			PutInt(0, 0);
			Send(0);
		}
	}

	//	Wypisywanie wyniku
	{
		if (id == 0) {
			int messanger = Receive(-1);
			cout << GetInt(messanger) << endl;
		}
	}
}