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

#include <iostream>
#include <algorithm>
#include <vector>

using ll = long long;

int main()
{
  int node = MyNodeId();

  int pipes = PipeHeight();
  int discs = NumberOfDiscs();

  int machines = NumberOfNodes();
  int needed = std::min(pipes / 100000 + 1, machines);

  if (node < needed) { // there is something to be done
    ll part = pipes / needed;
    ll start = node * part + 1;
    ll end = (node + 1) * part;  // inclusive

    if (node == needed - 1) {  // last
      end = pipes;
    }
        
    ll length = end - start + 1;
    std::vector<ll> dims(length);
    dims[0] = HoleDiameter(start);
    for (ll i = 1; i < length; ++i) {
      dims[i] = std::min(dims[i - 1], HoleDiameter(i + start));
    }

    if (node == 0 && needed > 1) {
      PutLL(node + 1, dims.back());
      Send(node + 1);
    }

    if (node != 0) {
      Receive(node - 1);
      ll value = GetLL(node - 1);

      ll lowest = std::min(value, dims.back());
      if (node != needed - 1) {
        PutLL(node + 1, lowest);
        Send(node + 1);
      }

      for (ll i = 0; i < length; ++i) {
        if (dims[i] > value) {
          dims[i] = value;
        } else {
          break;
        }
      }
    }

    ll di = 1;
    ll front = dims.front();
    ll last_disc = 0;

    if (node != needed - 1) {
      Receive(node + 1);
      di = GetLL(node + 1);

      if (di == -1) {
        if (node != 0) {
          PutLL(node - 1, -1);
          Send(node - 1);
        }
        return 0;  // solution found
      }
    }

    for (int i = length - 1; i >= 0 && di <= discs; --i) {
      ll d = DiscDiameter(di);
      if (d > front) { // no more discs in this node
        break;
      } else if (dims[i] >= d) {
        if (di == discs) {
          last_disc = start + i;
        }
        ++di;
      }
    }

    ll data = di;
    if (di > discs || (node == 0 && di <= discs)) {  // last disc was placed or it could not be placed
      std::cout << last_disc << std::endl;
      data = -1;
    }

    if (node != 0) {
      PutLL(node - 1, data);
      Send(node - 1);
    }
  }
  return 0;
}