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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
#include "message.h"
#include "krazki.h"

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <sstream>

using namespace std;

int tot_nodes;
int my_node;
int N_pipes;
int M_disks;

// required to create fictive 0-diameter after 
long long getHoleDiameter__(int idx)
{
//	fprintf(stderr, "my_node = %d tries to get hole diameter #%d...\t", my_node, idx);
	if(idx > N_pipes) {
//		fprintf(stderr, "it's ZERO because idx > N_pipes\n");
		return 0LL;
	} else {
		long long res = HoleDiameter((long long)idx);
//		fprintf(stderr, "it's %lld\n", res);
		return res;
	}
}

struct bottleneck_item
{
	int idx;
	long long diam;
	bottleneck_item(int i_, long long d_) : idx(i_), diam(d_) { } ;
};

//void print_logs(const string &comment_string, const vector<bottleneck_item> &bottlenecks)
//{
//	stringstream sstr;
//	sstr << comment_string << " : ";
//	for(int i = (int)bottlenecks.size()-1; i >= 0; i--) {
//		sstr << "(" << i << ":" << bottlenecks[i].idx << "->" << bottlenecks[i].diam << ")" << (i>0 ? "," : "\n");
//	}
//	string sbuff;
//	getline(sstr, sbuff);
//	fprintf(stderr, "%s\n", sbuff.c_str());
//}



int main(int argc, char* argv[])
{
	tot_nodes = NumberOfNodes();
	my_node = MyNodeId();
	N_pipes = (int)PipeHeight();
	M_disks = (int)NumberOfDiscs();
	if(M_disks > N_pipes) {
		if(my_node == 0) {
			printf("0\n");
		}
		return 0;
	}
	int start_idx_for_pipes = (int)(((double)N_pipes+1.25) * pow(((double)my_node / (tot_nodes)), 1.05));
	int after_fin_idx_for_pipes = (int)(((double)N_pipes+1.25) * pow(((1.0 + (double)my_node) / (tot_nodes)), 1.05));

//	int start_idx_for_disks = (int)(((double)N_pipes+1.25) * pow(((double)my_node / (tot_nodes)), 0.8));
//	int after_fin_idx_for_disks = (int)(((double)N_pipes+1.25) * pow(((1.0 + (double)my_node) / (tot_nodes)), 0.8));

//	static char buff[0x100];
//	sprintf(buff, "my_node = %d: start_idx_for_pipes = %d, after_fin_idx_for_pipes = %d, N_pipes = %d, M_disks = %d, hole[2] = %d, hole[5] = %d", my_node, start_idx_for_pipes, after_fin_idx_for_pipes, N_pipes, M_disks, getHoleDiameter__(2), getHoleDiameter__(5));
//	sprintf(buff, "my_node = %d: start_idx_for_pipes = %d, after_fin_idx_for_pipes = %d, N_pipes = %d, M_disks = %d", my_node, start_idx_for_pipes, after_fin_idx_for_pipes, N_pipes, M_disks);
//	fprintf(stderr, "%s\n", buff);

	vector<bottleneck_item> bottlenecks;
	for(int idx = after_fin_idx_for_pipes-1; idx >= start_idx_for_pipes; idx--) {
//		fprintf(stderr, "my_node = %d, starts iteration whe/re idx = %d\n", my_node, idx);
		long long curr_D = getHoleDiameter__(idx+1);
		while(!bottlenecks.empty() && curr_D < bottlenecks.back().diam) {
			bottlenecks.pop_back();
		}
		if(bottlenecks.empty() || curr_D > bottlenecks.back().diam)
			bottlenecks.push_back(bottleneck_item(idx, curr_D));
	}

//	print_logs("before messaging, pipes ", bottlenecks);

	long long min_of_prev_ranges;
	if(my_node > 0) {
		Receive(my_node-1);
		min_of_prev_ranges = GetLL(my_node-1);
	} else {
		min_of_prev_ranges = (long long)3e18;
	}
	long long min_of_prevs_and_this_ranges = min(min_of_prev_ranges, (bottlenecks.empty() ? (long long)3e18 : bottlenecks[0].diam));
	if(my_node < tot_nodes-1) {
		PutLL(my_node+1, min_of_prevs_and_this_ranges);
		Send(my_node+1);
	}
	while(!bottlenecks.empty() && bottlenecks.back().diam > min_of_prev_ranges) {
		bottlenecks.pop_back();
	}
	if(bottlenecks.empty()  || bottlenecks.back().idx > start_idx_for_pipes) {
		bottlenecks.push_back(bottleneck_item(start_idx_for_pipes, min_of_prev_ranges));
	}

//	print_logs("after messaging, pipes ", bottlenecks);

	int idx_of_disc;
	long long curr_hole_diam;
	int idx_of_hole_global = after_fin_idx_for_pipes-1;
	if(my_node == tot_nodes - 1) {
		idx_of_disc = 1;
		curr_hole_diam = 0LL;
	} else {
		Receive(my_node+1);
		idx_of_disc = GetInt(my_node+1);
//		curr_hole_diam = GetLL(my_node+1);
		curr_hole_diam = bottlenecks[0].diam;
//		fprintf(stderr, "my_node = %d received idx_of_disc = %d;     curr_hole_diam=%lld was set from bottlenecks\n", my_node, (int)idx_of_disc, (long long)curr_hole_diam);
		if(idx_of_disc < 0) { // result is already written by another instance
			if(my_node > 0) {
				PutInt(my_node-1, -1); // saying to other nodes that result is already written
				PutLL(my_node-1, curr_hole_diam);
				Send(my_node-1);
			}
			return 0; 
		}
	}
	if(M_disks - idx_of_disc > after_fin_idx_for_pipes - 1) { // TODO: recheck, maybe some \pm1 
		printf("0\n"); // all discs cannot fit to place left
//		fprintf(stderr, "printing ZERO because M_disks(%d) - idx_of_disc(%d) > after_fin_idx_for_pipes(%d) - 1", M_disks, idx_of_disc, after_fin_idx_for_pipes);
		if(my_node > 0) {
			PutInt(my_node-1, -1); // saying to other nodes that result is already written
//			PutLL(my_node-1, -1LL);
			Send(my_node-1);
		}
		return 0;
	} else {
		int idx_in_bottlenecks = 0;
		long long curr_disc_diam = DiscDiameter((long long)idx_of_disc);
		if(!bottlenecks.empty() && bottlenecks[0].idx >= idx_of_hole_global) {
//			fprintf(stderr, "!bottlenecks.empty() && bottlenecks[0].idx >= idx_of_hole_global\n");
			curr_hole_diam = bottlenecks[0].diam;
		}
		
		while(idx_of_hole_global >= start_idx_for_pipes) {
			if(curr_disc_diam <= curr_hole_diam) {
//				fprintf(stderr, "my_node=%d,  idx_of_disc=%d->curr_disc_diam=%lld,  idx_of_hole_global=%d->curr_hole_diam=%lld\n", 
//					my_node, (int)idx_of_disc, (long long)curr_disc_diam, (int)idx_of_hole_global, (long long)curr_hole_diam);
				if(idx_of_disc == M_disks) {
					printf("%d\n", idx_of_hole_global+1);
//					fprintf(stderr, "Standard output written when idx_of_disc:%d == M_disks:%d occured\n", idx_of_disc, M_disks);
					if(my_node > 0) {
						PutInt(my_node-1, -1); // saying to other nodes that result is already written
//						PutLL(my_node-1, (long long)3e18);
						Send(my_node-1);
					}
					return 0;
				}
				idx_of_disc++;
				idx_of_hole_global--;
				if(idx_in_bottlenecks+1 < (int)bottlenecks.size()  &&  
					idx_of_hole_global == bottlenecks[idx_in_bottlenecks+1].idx) 
				{
					idx_in_bottlenecks++;
					curr_hole_diam = bottlenecks[idx_in_bottlenecks].diam;
//					fprintf(stderr, "my_node=%d: went throw bottlenecks[%d]=(%d,%lld)\n", 
//						my_node, idx_in_bottlenecks, 
//						(int)(bottlenecks[idx_in_bottlenecks].idx), (long long)(bottlenecks[idx_in_bottlenecks].diam));
				}
				curr_disc_diam = DiscDiameter((long long)idx_of_disc);
			} else {
// #error re-check if this correct
				if(idx_in_bottlenecks+1 < (int)bottlenecks.size()  &&  bottlenecks[idx_in_bottlenecks].idx-1 >= start_idx_for_pipes) {
//					fprintf(stderr, "my_node=%d: used ready bottlenecks array to jump from idx_of_disc=%d->curr_disc_diam=%lld,  idx_of_hole_global=%d->curr_hole_diam=%lld\t", 
//						my_node, (int)idx_of_disc, (long long)curr_disc_diam, (int)idx_of_hole_global, (long long)curr_hole_diam);
					idx_in_bottlenecks++;
					curr_hole_diam = bottlenecks[idx_in_bottlenecks].diam;
					idx_of_hole_global = bottlenecks[idx_in_bottlenecks-1].idx-1;
//					fprintf(stderr, " to idx_in_bottlenecks=%d,  idx_of_disc=%d->curr_disc_diam=%lld,  idx_of_hole_global=%d->curr_hole_diam=%lld\n", idx_in_bottlenecks, idx_of_disc, curr_disc_diam, idx_of_hole_global, curr_hole_diam);				
				} else {
					if(my_node > 0) {
						PutInt(my_node-1, idx_of_disc);
//						PutLL(my_node-1, bottlenecks.back().diam);
						Send(my_node-1);
					} else { // my_node == 0
						printf("0\n");
//						fprintf(stderr, "my_node=%d: printing ZERO because idx_in_bottlenecks:%d >= bottlenecks.size():%d && my_node==0\n", 
//							my_node, idx_in_bottlenecks, bottlenecks.size());
					} 
					return 0;
				}
			}
		}
		if(my_node > 0) {
			PutInt(my_node-1, idx_of_disc);
//			PutLL(my_node-1, curr_hole_diam);
			Send(my_node-1);
		} else { // my_node == 0
			printf("%d\n", idx_of_hole_global+1);
//			fprintf(stderr, "Standard output written after loop finished normally\n");
		}
		return 0;
	}
	return 0;
}