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

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

using namespace std;


void slave() {
  int n = NumberOfNodes();
  int ii = MyNodeId();
  
  int s = n - 1;
  int h = PipeHeight();
  s = min(s, h);
  
  if(ii >= s) return;
  
  int i0 = 1 + h * ii       / s;
  int i1 =     h * (ii + 1) / s;
  
  vector<int64_t> pipe(i1 - i0 + 1);
  
  for(int i = i0; i <= i1; i++) pipe[i - i0] = HoleDiameter(i);
  
  for(int i = i0 + 1; i <= i1; i++) pipe[i - i0] = min(pipe[i - i0], pipe[i - i0 - 1]);
  
  PutLL(n-1, pipe[0]);
  Send(n-1);
  // cerr << "send " << ii << " -> " << n-1 << '\n';
  
  Receive(n-1);
  int64_t prev = GetLL(n-1);
  
  for(int i = i0; i <= i1; i++) pipe[i - i0] = min(prev, pipe[i - i0]);
  
  int k = NumberOfDiscs();
  
  int64_t iz = i1;
  
  while(true) {
    int src = Receive(-1);
    int j = GetInt(src);
    
    if(j == -1) return;
    
    while(j <= k) {
      int64_t d = DiscDiameter(j);
      // cerr << "ii = " << ii << ", Disc #" << j << " (" << d << ")\n";
      
      while(iz >= i0 and d > pipe[iz - i0]) iz--;
      
      if(iz >= i0) {
        if(j == k) {
          cout << max<int64_t>(iz, 0) << '\n';
          PutInt(n-1, -1);
          Send(n-1);
          // cerr << "send " << ii << " -> " << n-1 << '\n';
          break;
        }
      } else {
        if(ii == 0) {
          cout << "0\n";
          PutInt(n-1, -1);
          Send(n-1);
          // cerr << "send " << ii << " -> " << n-1 << '\n';
          break;
        } else {
          PutInt(ii-1, j);
          Send(ii-1);
          // cerr << "send " << ii << " -> " << ii-1 << '\n';
          break;
        }
      }
      
      iz--;
      j++;
    }
  }
}


void killSlaves() {
  int n = NumberOfNodes();
  int s = n - 1;
  int h = PipeHeight();
  s = min(s, h);
  
  for(int i = 0; i < s; i++) {
    PutInt(i, -1);
    Send(i);
  }
}


void master() {
  int n = NumberOfNodes();
  int s = n - 1;
  int h = PipeHeight();
  s = min(s, h);
  
  vector<int> tops;
  for(int i = 0; i < s; i++) {
    Receive(i);
    int64_t top = GetLL(i);
    tops.push_back(top);
    if(i != 0) tops[i] = min(tops[i], tops[i-1]);
  }
  
  for(int i = 0; i < s; i++) {
    PutLL(i, i == 0 ? numeric_limits<int64_t>::max() : tops[i-1]);
    Send(i);
  }
  
  int z = tops.size() - 1;
  PutInt(z, 1);
  Send(z);
  
  int src = Receive(-1);
  int j = GetInt(src);
  
  if(j == -1) killSlaves();
}


int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  int n = NumberOfNodes();
  
  if(MyNodeId() != n-1) {
    slave();
  } else {
    master();
  }
  
  return 0;
}