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

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

long long min(long long a, long long b){
  return a < b ? a : b;
}

int max(int a, int b){
  return a > b ? a : b;
}

int main(){
  int i;
  int nodes = NumberOfNodes();
  int pipes = PipeHeight();
  int all_discs = NumberOfDiscs();
  int my_id = MyNodeId();
  int segment = max(2000000, (pipes+nodes-1)/nodes);
  // printf("[%d]nodes %d pipes %d segment %d\n", my_id, nodes, pipes, segment);
  long long widths[segment];
  long long minimums[segment];
  long long minimumFromParent;

  // printf("pipes are %d\n", pipes);
  // printf("My Id is %d\n",my_id);

  int start = my_id * segment;
  int end = (my_id + 1) * segment;

  int last_node_id = max((pipes-1)/segment, 0);

  if (pipes <= start){
    // printf("[%d]Nothing to do for me - exiting\n", my_id);
    return EXIT_SUCCESS;
  }

  if (end > pipes){
    end = pipes;
  }

  int len = end - start;

  // printf("[%d]Start %d - End %d\n", my_id, start, end);

  for (i = start; i<end; i++){
    widths[i-start] = HoleDiameter(i+1);
  }

  // printf("[%d]Wczytalem tablice\n", my_id);
  // for (i=start;i<end;i++){
    // printf("[%d] width %d is %lld\n", my_id, i, widths[i-start]);
  // }

  if (my_id > 0){
    // printf("[%d]I need to wait for minimum input-in \n", my_id);
    Receive(my_id-1);
    minimumFromParent = GetLL(my_id-1);
    // printf("[%d]Przeczytalem minimum %lld od poprzedniej instacji\n", my_id, minimumFromParent);
  } else {
    minimumFromParent = (1e18) + 1;
  }

  minimums[0] = min(widths[0], minimumFromParent);
  for (i = start+1;i<end;i++){
    minimums[i-start] = min(minimums[i-start-1], widths[i-start]);
  }

  // printf("[%d]Wczytalem minima\n", my_id);
  // for (i=start;i<end;i++){
    // printf("[%d] minimum %d is %lld\n", my_id, i, minimums[i-start]);
  // }

  if (my_id < last_node_id){
    // printf("[%d]Przesylam moje minimum %lld do nastepnej instancji %d\n", my_id, minimums[len-1], my_id+1);
    PutLL(my_id+1, minimums[len-1]);
    Send(my_id+1);  
  }

  int currentDisc;

  if (my_id == last_node_id){
      currentDisc = 1;
  } else {
    // printf("[%d]Czekam na id obecnego krazka\n", my_id);
    Receive(my_id+1);
    currentDisc = GetInt(my_id+1);
    if (currentDisc == -1){
      // printf("[%d]Brak krazka, to znaczy ze odp jest juz znana\n", my_id);
    } else {
      // printf("[%d]Obecny krazek %d od instacji %d\n", my_id, currentDisc, my_id+1);  
    }
  }

  if (currentDisc != -1){
    // printf("[%d] Przetwarzam\n", my_id);
    long long krazekWidth = DiscDiameter(currentDisc);
    for (i = end-1; i>=start; i--){
      if (minimums[i-start]>=krazekWidth){
        // printf("[%d]Krazek %d of szerokosci %lld wyladuje na szczeblu %d o szerokosci %lld\n", 
               // my_id, currentDisc, krazekWidth, i+1, minimums[i-start]);
        if (currentDisc == all_discs){
          // printf("[%d]Znalazlem odpowiedz wypisuje ja = %d\n", my_id, i+1);
          std::cout << (i+1) << std::endl;
          currentDisc = -1;
          break;
        } else {
          currentDisc++;
          krazekWidth = DiscDiameter(currentDisc);
        }
      }
    }
  } 

  if (my_id > 0){
    // printf("[%d]Przesylam obecny krazek %d do nastepnej instancji %d\n", my_id, currentDisc, my_id-1);
    PutInt(my_id-1, currentDisc);
    Send(my_id-1);   
  } else {
    if (currentDisc != -1){
      std::cout << 0 << std::endl;
    }
  }

  return EXIT_SUCCESS;
}

// int main() {
//   // Tylko zerowy komputer coś liczy.
//   if (MyNodeId() != 0) {
//     return EXIT_SUCCESS;
//   }
//   int depth;
//   long long int max_disc_diameter = 0;
//   for (int i = 1; i <= NumberOfDiscs(); i++) {
//     max_disc_diameter = std::max(max_disc_diameter, DiscDiameter(i));
//   }
//   if (HoleDiameter(PipeHeight()) < max_disc_diameter) {
//     depth = 0;
//   } else {
//     depth = std::max(0, PipeHeight() - NumberOfDiscs() + 1);
//   }
//   std::cout << depth << std::endl;
//   return EXIT_SUCCESS;
// }