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
#include <iostream>
#include "message.h"
#include "krazki.h"

typedef long long int lli;

lli n;
lli m;

lli id = MyNodeId();
lli nodes = NumberOfNodes();

bool master = (id == 0);

lli startR, endR, lenR;

lli *holes;
lli *discs;

void run()
{
  startR = id * n / nodes + 1;
  endR = (id+1) * n / nodes + 1;
  lenR = endR - startR;
  holes = new lli[endR - startR + 118];

  holes[0] = HoleDiameter(startR);

  for(int i=1; i<lenR; i++)
    holes[i] = std::min(holes[i - 1], HoleDiameter(startR + i));
  
  if(id > 0)
  {
    Receive(id - 1);
    lli m = GetLL(id - 1);
    holes[lenR - 1] = std::min(holes[lenR - 1], m);
    if(id +1 < nodes)
    {
      PutLL(id + 1, holes[lenR - 1]);
      Send(id + 1);
    }

    for(int i=0; i<lenR && holes[i] > m; i++)
      holes[i] = m;
  }
  else if(id + 1 < nodes)
  {
    PutLL(id + 1, holes[lenR - 1]);
    Send(id + 1);
  }

  int j = 1;
  if(id != nodes -1)
  {
    Receive(id + 1);
    char c = GetChar(id + 1);
    if(c == 1)
    {
      if(id != 0)
      {
        PutChar(id - 1, 1);
        Send(id - 1);
      }
      return;
    }
    j = GetInt(id + 1);
  }
  int poprzedni = endR;
  while(j <= m)
  {
    lli d = DiscDiameter(j);
    int a = poprzedni - 1;
    while(a >= startR && a < endR && holes[a - startR] < d)
      a --;
    poprzedni = a;
    if(poprzedni < startR)
    {
      if(poprzedni == 0)
      {
        if(id != 0)
        {
          PutChar(id - 1, 1);
          Send(id - 1);
        }
        std::cout << 0 << std::endl;
        return; 
      }
      else
      {
        PutChar(id - 1, 0);
        PutInt(id - 1, j);
        Send(id - 1);
        return;
      }
    }
    j ++;
  }
  if(id != 0)
  {
    PutChar(id - 1, 1);
    Send(id - 1);
  }
  std::cout << poprzedni << std::endl;
}

int main()
{
  n = PipeHeight();
  m = NumberOfDiscs();

  if(n < m)
  {
    if(master)
      std::cout << 0 << std::endl;
    return 0;
  }

  if(n < nodes)
  {
    nodes = n;
    if(id >= nodes)
      return 0;
  }

  run();

  return 0;
}