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
#include "bits/stdc++.h"

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

using namespace std;
using LL = long long;

int ExtendedPipeHeight() {return PipeHeight() + 1;}
int ExtendedHoleDiameter(int n, int i) {return (i == n) ? 0 : HoleDiameter(i);}


int main() {
  int n_buckets = 0;
  int number_of_nodes = NumberOfNodes();
  int rect_ratio = min(4, number_of_nodes);
  while(rect_ratio * (n_buckets + 1) * (n_buckets + 1) <= number_of_nodes) ++n_buckets;
  number_of_nodes = rect_ratio * n_buckets * n_buckets;
  int my_node_id = MyNodeId();
  if(my_node_id >= number_of_nodes) return EXIT_SUCCESS;
  int n = ExtendedPipeHeight();
  int m = NumberOfDiscs();
  int r = my_node_id % (rect_ratio * n_buckets); // [0, rect_ratio * n_buckets)
  int c = my_node_id / (rect_ratio * n_buckets); // [0, n_buckets)

  int i0 = 1 + (LL) r * n / (rect_ratio * n_buckets);
  int i1 = 1 + (LL) (r + 1) * n / (rect_ratio * n_buckets);
  vector<pair<LL, int>> v; v.reserve(i1-i0);
  for(int i = i0; i < i1; ++i){
    LL r = ExtendedHoleDiameter(n, i);
    if(v.empty() || v.back().first > r){
      v.emplace_back(r, i);
    }
  }

  int j0 = 1 + (LL) c * m / n_buckets;
  int j1 = 1 + (LL) (c + 1) * m / n_buckets;
  int best = n;
  int l = v.size();
  for(int j = j0; j < j1; ++j) {
    int k = DiscDiameter(j);
    while(l > 0 && v[l-1].first < k) --l;
    if(l < (int) v.size()) {
      int i = v[l].second;
      int cand = max(0, i - (m - (j - 1)));
      best = min(best, cand);
    }
  }
  if (my_node_id != 0) {
    PutInt(0, best);
    Send(0);
  } else {
    for(int i = 1; i < number_of_nodes; ++i) {
      Receive(i);
      int i_best = GetInt(i);
      best = min(best, i_best);
    }
    printf("%d\n", max(best, 0));
  }
  return EXIT_SUCCESS;
}