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
#include <cstdlib>
#include <iostream>
#include <vector>

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

using namespace std;

const long long kTen = 10;
const long long kHundred = kTen * kTen;
const long long kThousand = kTen * kHundred;
const long long kMillion = kThousand * kThousand;
const long long kBillion = kThousand * kMillion;
const long long kInfinity = kBillion * kBillion;

int nodes;
long long pipe_height;

void Split(const long long a, vector<long long> *segments) {
  // cerr << "Splitting " << a << " into " << nodes << " pieces:";
  for (int i = 0; i <= nodes; ++i) {
    segments->push_back((a * i) / nodes);
    // cerr << ' ' << segments->back();
  }
  // cerr << endl;
}

long long HoleDiameterCapped(const long long i) {
  if (i < 0) return kInfinity;
  if (i >= pipe_height) return 0;
  return HoleDiameter(i + 1);
}

int main() {
  const int node = MyNodeId();
  nodes = NumberOfNodes();

  pipe_height = PipeHeight();

  vector<long long> pipe_segments;
  Split(pipe_height, &pipe_segments);

  // Compute effective bottom diameter of each pipe segment, send to node 0.
  {
    vector<long long> my_diameter;
    for (int i = pipe_segments[node]; i < pipe_segments[node + 1]; ++i) my_diameter.push_back(HoleDiameterCapped(i));
    for (int i = 1; i < my_diameter.size(); ++i) my_diameter[i] = min(my_diameter[i], my_diameter[i - 1]);
    /*
    cerr << "hole shard " << node << ':';
    for (int i = 0; i < my_diameter.size(); ++i) cerr << ' ' << my_diameter[i];
    cerr << endl;
    */
    const long long pipe_segment_diameter = my_diameter.empty() ? kInfinity : my_diameter.back();
    PutLL(0, pipe_segment_diameter);
    Send(0);
  }
  // cerr << 'A' << node << endl;

  // Node 0: Aggregate diameters, broadcast.
  if (node == 0) {
    vector<long long> pipe_segment_diameter(1, kInfinity);
    for (int i = 0; i < nodes; ++i) {
      Receive(i);
      const long long diameter = GetLL(i);
      pipe_segment_diameter.push_back(min(pipe_segment_diameter.back(), diameter));
    }
    for (int i = 0; i < nodes; ++i) {
      for (int j = 0; j < pipe_segment_diameter.size(); ++j) PutLL(i, pipe_segment_diameter[j]);
      Send(i);
    }
  }
  // cerr << 'B' << node << endl;

  // Receive aggregated diameters from node 0.
  vector<long long> pipe_segment_diameter;
  Receive(0);
  for (int i = 0; i <= nodes; ++i) pipe_segment_diameter.push_back(GetLL(0));

  // cerr << 'C' << node << endl;

  vector<long long> disc_segments;
  Split(NumberOfDiscs(), &disc_segments);

  // Determine the lowest top position of each disc segment, send to node 0.
  {
    vector<long long> disc_diameter;
    for (int i = disc_segments[node]; i < disc_segments[node + 1]; ++i) disc_diameter.push_back(DiscDiameter(i + 1));
    for (int i = 1; i < disc_diameter.size(); ++i) disc_diameter[i] = max(disc_diameter[i], disc_diameter[i - 1]);
    /*
    cerr << "disc shard " << node << ':';
    for (int i = 0; i < disc_diameter.size(); ++i) cerr << ' ' << disc_diameter[i];
    cerr << endl;
    */

    const long long disc_segment_top_diameter = disc_diameter.empty() ? 0 : disc_diameter.back();

    // Determine lowest good and highest bad pipe segment diameters.
    int segment_can = pipe_segment_diameter.size() - 1;
    while (segment_can >= 0 && pipe_segment_diameter[segment_can] < disc_segment_top_diameter) --segment_can;
    int segment_cant = 0;
    while (segment_cant + 1 < pipe_segment_diameter.size() && pipe_segment_diameter[segment_cant] >= disc_segment_top_diameter) ++segment_cant;

    // cerr << "segments: can " << segment_can << ", can't " << segment_cant << endl;

    // Our disc stack fits from here up, determine the highest disc depth.
    int level_can = pipe_segments[segment_can] - disc_diameter.size();
    // Our disc stack does not fit from here down, determine the lowest disc depth.
    int level_cant = pipe_segments[segment_cant] + disc_diameter.size();

    // Push the good level up to segment diameter.
    while (segment_can >= 0 && pipe_segments[segment_can] > level_can) --segment_can;
    if (segment_can >= 0) level_can = pipe_segments[segment_can];

    // cerr << "levels: can " << level_can << ", can't " << level_cant << endl;

    // 1 corresponds to level_can.
    vector<long long> hole_diameter;
    hole_diameter.push_back(segment_can < 0 ? kInfinity : pipe_segment_diameter[segment_can]);
    for (int i = level_can; i <= level_cant; ++i) hole_diameter.push_back(min(hole_diameter.back(), HoleDiameterCapped(i)));

    /*
    cerr << "work buffer starting at " << level_can - 1 << ':';
    for (int i = 0; i < hole_diameter.size(); ++i) cerr << ' ' << hole_diameter[i];
    cerr << endl;
    */

    int hole_index = hole_diameter.size() - 1;
    for (int i = 0; i < disc_diameter.size(); ++i) {
      while (disc_diameter[i] > hole_diameter[hole_index]) --hole_index;
      --hole_index;
    }

    // cerr << "shard " << node << " must end at " << level_can + hole_index << " or higher" << endl;
    PutLL(0, level_can + hole_index);
    Send(0);
  }
  // cerr << 'D' << node << endl;

  // Aggregate results and print out the answer.
  if (node == 0) {
    long long ret = pipe_height;
    for (int i = 0; i < nodes; ++i) {
      ret += disc_segments[i];
      ret -= disc_segments[i + 1];
      Receive(i);
      ret = min(ret, GetLL(i));
    }
    cout << max(0LL, ret + 1) << endl;
    return 0;
  }

  return 0;
}