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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#include <algorithm>
#include <cstdio>
#include <vector>

#include "message.h"
#include "krazki.h"
using namespace std;

int constexpr root_node = 0;
int hole_range_begin, hole_range_end;
vector<long long> hole_fixed_diameter;

int answerDiameter(long long const diameter) {
	auto it = upper_bound(hole_fixed_diameter.begin(), hole_fixed_diameter.end(), diameter, greater<long long>()); // first element lower than diameter
	return hole_range_begin + distance(hole_fixed_diameter.begin(), it) - 1;
}

int answerQueryRoot(vector<long long> const & root_hole_fixed_diameter, int const query) {
	if(query == -1)
		return -1;

	long long const diameter = DiscDiameter(query);
	auto it = upper_bound(root_hole_fixed_diameter.begin(), root_hole_fixed_diameter.end(), diameter, greater<long long>()); // first element lower than diameter
	int const node = distance(root_hole_fixed_diameter.begin(), it);
//	if(diameter == 1e18)
//		printf("1e18 node: %i\n", node);

	if(node == NumberOfNodes())
		return PipeHeight();
	else if(node == 0)
		return answerDiameter(diameter);
	else {
        PutInt(node, query);
        Send(node);
        Receive(node);
        return GetInt(node);
	}
}

int main() {
    hole_range_begin = static_cast<long long>(PipeHeight()) * (MyNodeId()) / (NumberOfNodes()) + 1;
    hole_range_end = static_cast<long long>(PipeHeight()) * (MyNodeId() + 1) / (NumberOfNodes()) + 1;
    int const disc_range_begin = static_cast<long long>(NumberOfDiscs()) * (MyNodeId()) / (NumberOfNodes()) + 1;
    int const disc_range_end = static_cast<long long>(NumberOfDiscs()) * (MyNodeId() + 1) / (NumberOfNodes()) + 1;

    hole_fixed_diameter.reserve(hole_range_end - hole_range_begin);

    hole_fixed_diameter.emplace_back(HoleDiameter(hole_range_begin));
    if(hole_range_begin != hole_range_end)
		for(auto i = hole_range_begin + 1 ; i != hole_range_end ; ++i)
			hole_fixed_diameter.emplace_back(min(hole_fixed_diameter.back(), HoleDiameter(i)));

    long long max_diameter = -1;
    int max_index = -1, max_pos;
	for(auto j = disc_range_begin ; j != disc_range_end ; ++j) {
        long long const diameter = DiscDiameter(j);
        if(diameter >= max_diameter) {
			max_diameter = diameter;
			max_index = j;
        }
	}

	if(MyNodeId() == root_node) {
//		printf("t1\n");
        vector<long long> root_hole_fixed_diameter;
        vector<int> queries;
		root_hole_fixed_diameter.reserve(NumberOfNodes());
		queries.reserve(NumberOfNodes());

		root_hole_fixed_diameter.emplace_back(hole_fixed_diameter.back());
		queries.emplace_back(max_index);
//		printf("t2\n");
		for(int node = 1 ; node != NumberOfNodes() ; ++node) {
            Receive(node);
            root_hole_fixed_diameter.emplace_back(min( root_hole_fixed_diameter.back(), GetLL(node) ));
            queries.emplace_back(GetInt(node));
		}

		max_pos = answerQueryRoot(root_hole_fixed_diameter, max_index);
//		printf("t3\n");
		int receive_count = 0;
		for(int node = 1 ; node != NumberOfNodes() ; ++node)
            queries[node] = answerQueryRoot(root_hole_fixed_diameter, queries[node]);

//		printf("t4\n");
        for(int node = 1 ; node != NumberOfNodes() ; ++node) {
			PutInt(node, -2);
			PutInt(node, queries[node]);
			Send(node);
        }
//		printf("t5\n");
	} else {
		PutLL(root_node, hole_fixed_diameter.back());
        PutInt(root_node, max_index);
        Send(root_node);

//		printf("t6\n");
        while(true) {
			Receive(0);
			auto const query = GetInt(0);
			if(query == -2)
				break;
			PutInt(0, answerDiameter(DiscDiameter(query)));
			Send(0);
        }
//		printf("t7\n");
        max_pos = GetInt(0);
	}

//	printf("MyNodeId(): %i, max_diameter: %lli, max_index: %i, max_pos: %i\n", MyNodeId(), max_diameter, max_index, max_pos);
//	printf("MyNodeId(): %i, hole_range_begin: %i, hole_range_end: %i\n", MyNodeId(), hole_range_begin, hole_range_end);
//	printf("MyNodeId(): %i, disc_range_begin: %i, disc_range_end: %i\n", MyNodeId(), disc_range_begin, disc_range_end);



	int min_top_pos = max_pos - NumberOfDiscs() + max_index;
//	printf("MyNodeId(): %i, (before) min_top_pos: %i\n", MyNodeId(), min_top_pos);

	if(max_pos == -1)
		min_top_pos = 1 << 30;
	else {

		hole_range_begin = max_pos;
		hole_range_end = min(max_pos + max_index - disc_range_begin + 2, PipeHeight() + 1);

//		printf("MyNodeId(): %i, hole_range_begin: %i, hole_range_end: %i\n", MyNodeId(), hole_range_begin, hole_range_end);

		hole_fixed_diameter.clear();
		hole_fixed_diameter.reserve(hole_range_end - hole_range_begin);

		hole_fixed_diameter.emplace_back(HoleDiameter(hole_range_begin));
		for(auto i = hole_range_begin + 1 ; i != hole_range_end ; ++i)
			hole_fixed_diameter.emplace_back(min(hole_fixed_diameter.back(), HoleDiameter(i)));

//		printf("MyNodeId(): %i, DiscDiameter(disc_range_begin): %lli, answerDiameter(DiscDiameter(disc_range_begin)): %i\n", MyNodeId(), DiscDiameter(disc_range_begin), answerDiameter(DiscDiameter(disc_range_begin)));

		for(auto j = disc_range_begin ; j != max_index ; ++j)
			min_top_pos = min(min_top_pos, answerDiameter(DiscDiameter(j)) - NumberOfDiscs() + j);

	}

//	printf("MyNodeId(): %i, (after) min_top_pos: %i\n", MyNodeId(), min_top_pos);

	if(MyNodeId() == 0) {
        int receive_count = 0;
        while(++receive_count != NumberOfNodes()) {
			auto const receive_id = Receive(-1);
			min_top_pos = min(min_top_pos, GetInt(receive_id));
        }
        printf("%i", max(min_top_pos, 0));
        return 0;
	} else {
		PutInt(0, min_top_pos);
		Send(0);
		return 0;
	}
}