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
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
using namespace std;

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

typedef long long ll;

int nodes, my_id;

const int HOLE = 0, DISC = 1;

struct GURU_RUR {
	int type;
	int n;
	vector<int> from; // 0 ... nodes
	vector<ll> worst; // 0 ... nodes-1
	vector<ll> values;
	long long get(int i) {
		return type == HOLE ? HoleDiameter(i + 1) : DiscDiameter(i + 1);
	}
	void read() {
		n = type == HOLE ? PipeHeight() :  NumberOfDiscs();
		from.resize(nodes + 1);
		worst.resize(nodes);
		for(int i = 0; i <= nodes; ++i)
			from[i] = (ll) n * i / nodes;
		
		auto consider = [&] (ll & a, ll b) {
			type == HOLE ? a = min(a, b) : a = max(a, b);
		};
		values.resize(from[my_id+1] - from[my_id]);
		// 'tmp' is something like 'worst[my_id]'
		ll tmp = get(from[my_id]);
		for(int i = 0; i < (int) values.size(); ++i) {
			consider(tmp, get(from[my_id] + i));
			values[i] = tmp;
		}
		for(int i = 0; i < nodes; ++i) {
			PutLL(i, tmp);
			Send(i);
		}
		for(int i = 0; i < nodes; ++i) {
			Receive(i);
			worst[i] = GetLL(i);
		}
		if(my_id != 0) {
			tmp = worst[0];
			for(int i = 0; i < my_id; ++i) consider(tmp, worst[i]);
			for(ll & x : values) consider(x, tmp);
		}
		//printf(type == HOLE ? "holes: " : "discs: ");
		//for(ll x : values) printf("%lld ", x);
		//puts("");
	}
} holes{HOLE}, discs{DISC};

void solve(int & ans) {
	if(holes.values.empty()) return;
	int where = 0;
	while(where < (int) discs.worst.size()
			&& discs.worst[where] <= holes.values.back())
		++where;
	if(where == (int) discs.worst.size()) return;
	// printf("where = %d\n", where);
	//int i_hole = holes.from[my_id+1] - 1;
	int i_disc = discs.from[where];
	ll big = 0;
	for(int i = 0; i < where; ++i)
		big = max(big, discs.worst[i]);
	assert(big <= holes.values.back());
	while(big <= holes.values.back())
		big = max(big, discs.get(i_disc++));
	--i_disc;
	// printf("i_disc = %d\n", i_disc);
	//puts("start");
	for(int ii = (int) holes.values.size() - 1; ii >= 0; --ii) {
		while(ii - 1 >= 0 && holes.values[ii-1] < big)
			--ii;
		ll hole = holes.values[ii];
		//printf("hole = %lld, big = %lld\n", hole, big);
		//if(hole >= big) return;
		//printf("%lld < %lld\n", hole, big);
		ans = min(ans, holes.from[my_id] + ii - (discs.n - i_disc) + 1);
		if(i_disc == discs.n - 1) return;
		big = max(big, discs.get(++i_disc));
	}
}

int main() {
	nodes = NumberOfNodes();
	my_id = MyNodeId();
	
	holes.read();
	discs.read();
	
	int ans = holes.n - discs.n + 1;
	solve(ans);
	
	PutInt(0, ans);
	Send(0);
	if(my_id != 0) return 0;
	for(int i = 0; i < nodes; ++i) {
		Receive(i);
		ans = min(ans, GetInt(i));
	}
	printf("%d\n", max(ans, 0));
}