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
#include <bits/stdc++.h>
#include "krazki.h"
#include "message.h"
using namespace std;
#define e1 first
#define e2 second
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false)
#define eb emplace_back
#define OUT(x) {cout << x; exit(0); }
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define scanf(...) scanf(__VA_ARGS__)?:0
typedef long long int ll;
typedef unsigned long long ull;
typedef pair <int, int> PII;
typedef pair <ll, ll> PLL;
typedef pair <PLL, int> PLLI;
typedef pair <PLL, PLL> PP;
typedef pair <PII, int> PPI;
typedef pair <ll, int> PLI;
typedef unsigned int ui;
const int inf = 1e9+9;
const ll MOD = 1e9+696969;
const long long INF = 1e18+3;
int n, m, k, a, b, c;

#define maxn 3000100
ll pref[maxn];
int main() {
	n = PipeHeight();
	int inst = NumberOfNodes(), ID = MyNodeId();
	int dl = n / inst + 1;
	int x = ID * dl + 1, y = min(n, ID * dl + dl);
	//first step comPutes partial mins for given range
	FOR(i, x, y) {
		pref[i - x] = HoleDiameter(i);
		if (i > x) pref[i - x] = min(pref[i - x], pref[i - x - 1]);
	}
	ll MIN = pref[y - x], popPref = INF;
	//send partial mins to other instances
	if (ID != 0) {
		Receive(ID - 1);
		popPref = GetLL(ID - 1);
		MIN = min(MIN, popPref);
	}
	if (ID != inst - 1) {
		PutLL(ID + 1, MIN);
		Send(ID + 1);
	}

	//correct partial sum in my instance
	pref[0] = min(pref[0], popPref);
	FOR(i, x + 1, y) pref[i - x] = min(pref[i - x], pref[i - x - 1]);
	int m = NumberOfDiscs();
	if (m > n) {
		if (ID == 0) cout << 0;
		exit(0);
	}

	//findAnswer 
	int krazek = 1, wysokosc;
		if (ID != inst - 1) {
			Receive(ID + 1);
			krazek = GetLL(ID + 1);
		}
		///cout << "ID: " << ID << ' ' << krazek << endl;
		if (krazek == -1) {
			if (ID == 0) exit(0);
			else {PutLL(ID-1, -1); Send(ID - 1); exit(0); }
		}
		else {
			wysokosc = y + 1;
			if (x <= y)
			FOR(j, krazek, m) {
				ll kj = DiscDiameter(j);
				int i = wysokosc - 1;
				while (i >= x && pref[i - x] < kj) --i;
				if (i < x) break;
				wysokosc = i;
				krazek = j + 1;
				if (j == m) {
					cout << wysokosc;
					if (ID > 0) {
						PutLL(ID - 1, - 1);
						Send(ID - 1);
					}
					exit(0);
				}
			}

			if (ID == 0) {
				cout << 0;
				exit(0);
			}
			else {
				PutLL(ID-1, krazek);
				Send(ID-1);
				exit(0);
			}
		}
}