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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
#include <cstdlib>
#include <cstdio>

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

#define LL long long int
#define MIN(X,Y) (((X)<(Y))?(X):(Y))
#define MAX(X,Y) (((X)>(Y))?(X):(Y))

long long int hole_diameters[10000010];
long long int hole_mins[110];
long long int disc_maxes[110];
long long int n;
long long int m;
int node_number;
int all_nodes;
long long int upper_hole_i;
long long int lower_hole_i;

int lower_disc_section;
int upper_disc_section;


long long int upper_hole_index(int node_no) {
  return n * node_no / all_nodes + 1;
}

long long int lower_hole_index(int node_no) {
  return MAX(upper_hole_index(node_no), n * (node_no + 1) / all_nodes);
}

long long int lower_disc_index(int node_no) {
  return m * (node_no) / all_nodes + 1;
}

long long int upper_disc_index(int node_no) {

  LL res =  MAX(lower_disc_index(node_no), m * (node_no + 1) / all_nodes);
  ////fprintf(stderr, "Dla node'a %d gdy nodeów jest %d zwracam wynik %lld\n", node_no, all_nodes, res);
  return res;
}

long long int get_hole_mins(int node_no) {
  if (node_no < 0)
    return 3000000000000000000;
  else
    return hole_mins[node_no];
}

long long int count_discs_in_sections(int lower, int upper) {
  if (lower >= upper - 1) {
    return 0;
  } else {
    return upper_disc_index(upper) - lower_disc_index(lower) + 1;
  }
}

long long int pipe_section_height() {
  return MAX(1, n / all_nodes);
}

void send_lower_section(int node_no, int lower_section) {
  if (node_no < all_nodes - 1)
    PutInt(node_no, lower_section);
  else
    lower_disc_section = lower_section;
}

void send_upper_section(int node_no, int upper_section) {
  if (node_no < all_nodes - 1) {
    PutInt(node_no, upper_section);
    Send(node_no);
  } else {
    upper_disc_section = upper_section;
  }
}

int main() {
  // how many nodes compute solution
  all_nodes = NumberOfNodes();
  // number of current node (0 - all_nodes-1)
  node_number = MyNodeId();

  // get problem's input data
  n = PipeHeight();
  m = NumberOfDiscs();

  if (n < m) {
    if (node_number != 0) {
      return EXIT_SUCCESS;
    }
    printf("0\n");
    return EXIT_SUCCESS;
  }

  // how many nodes compute solution
  all_nodes = NumberOfNodes();
  // number of current node (0 - all_nodes-1)
  node_number = MyNodeId();
  // reduce node numbers on small test cases
  if (n < 100000) {
    all_nodes = 1;
    if (node_number > 0) {
      return EXIT_SUCCESS;
    }
  }

/* usage of disc and hole diameters
  long long int disc_diameter = DiscDiameter(i); //(1 <= i <= m)
  long long int hole_diameter = HoleDiameter(j); //(1 <= j <= n)
*/

/* usage of message library
PutChar(int target, char value);
PutInt(int target, int value);
PutLL(int target, long long int value);

Send(int target); -- send stored values to target
Receive(int source); -- receive message from source or wait until it appears

Send and Receive works like FIFO

char GetChar(int source);
int  GetInt(int source);
long long int GetLong(int source);
*/

  // większy indeks - niżej w rurce
  // prasowanie rurki
  upper_hole_i = upper_hole_index(node_number);
  lower_hole_i = lower_hole_index(node_number);

  hole_diameters[0] = HoleDiameter(upper_hole_i);
  LL min_diameter = hole_diameters[0];
  for (LL i = upper_hole_i+1; i <= lower_hole_i; ++i) {
    hole_diameters[i-upper_hole_i] = HoleDiameter(i);
    if (hole_diameters[i-upper_hole_i] < min_diameter) {
      min_diameter = hole_diameters[i-upper_hole_i];
    } else {
      hole_diameters[i-upper_hole_i] = min_diameter;
    }
  }
  
  hole_mins[node_number] = min_diameter;
  // poczekanie na miny od tego wyżej
  if (node_number > 0) {
    Receive(node_number-1);
    for(int i = 0; i < node_number; ++i) {
      //fprintf(stderr, "Odbieram longa od %d\n", node_number-1);
      hole_mins[i] = GetLL(node_number-1);
    }
    hole_mins[node_number] = MIN(hole_mins[node_number-1], hole_mins[node_number]);
  }
  // wysyłanie minów temu niżej
  if (node_number < all_nodes - 1) {
    for(int i = 0; i <= node_number; i++) {
      //fprintf(stderr, "Wysyłam longa do %d\n", node_number+1);
      PutLL(node_number+1, hole_mins[i]);
    }
    Send(node_number+1);
  }
  // node all_nodes - 1 powinien mieć teraz wszystkie miny otworów
  // niech se każdy spłaszczy teraz końcówki przez hole diameters
  if (node_number > 0) {
    hole_diameters[0] = MIN(hole_diameters[0], hole_mins[node_number-1]);
    for(LL i = 1; i <= lower_hole_i - upper_hole_i; ++i) {
      hole_diameters[i] = MIN(hole_diameters[i-1], hole_diameters[i]);
    }
  }

  // liczenie maksów dysków
  LL lower_disc_i = lower_disc_index(node_number);
  LL upper_disc_i = upper_disc_index(node_number);
  LL max_diameter = 0;
  for(LL i = lower_disc_i; i <= upper_disc_i; ++i) {
    ////fprintf(stderr, "Pytam o dysk %lld, m=%lld\n", i, m);
    max_diameter = MAX(max_diameter, DiscDiameter(i));
  }
  disc_maxes[node_number] = max_diameter;
  
  // czekanie na maksy od tego wyżej
  if (node_number > 0) {
    Receive(node_number-1);
    for(int i = 0; i < node_number; ++i) {
      //fprintf(stderr, "Odbieram longa od %d\n", node_number-1);
      disc_maxes[i] = GetLL(node_number-1);
    }
    disc_maxes[node_number] = MAX(disc_maxes[node_number-1], disc_maxes[node_number]);
  }
  // wysyłanie maksów temu niżej
  if (node_number < all_nodes - 1) {
    for (int i = 0; i <= node_number; i++) {
      //fprintf(stderr, "Wysyłam longa do %d\n", node_number+1);
      PutLL(node_number+1, disc_maxes[i]);
    }
    Send(node_number+1);
  }
  // obliczanie sekcji krytycznych (przez tego najniżej)
  int lower_section = 0;
  // wysłanie sekcji krytycznych tym wyżej)
  if (node_number == all_nodes - 1) {
    // dla każdego węzła wyznacz jakie kawałki sklejonych dysków mogłyby
    // się na nim zablokować
    // 0-rowy node trzyma dane o wlocie rurki, a lecimy od dna
    int current_disc_section = 0;
    for(int node_no = all_nodes - 1; node_no  >= 0; --node_no) {
      lower_section = current_disc_section;
      send_lower_section(node_no, current_disc_section);
      // sprawdzenie, czy dyski z danej sekcji zablokują się na tym kawałku rurki, czy wyższym
      while(disc_maxes[current_disc_section] <= get_hole_mins(node_no-1)
        && count_discs_in_sections(lower_section, current_disc_section) <= pipe_section_height()
        && current_disc_section < all_nodes -1) {
        current_disc_section++;
      }
      //fprintf(stderr, "Wysyłam dwa inty do node'a %d\n", node_no);
      send_upper_section(node_no, current_disc_section);
    }
  }
  // odbieranie sekcji krytycznych od node'a o numerze: (all_nodes - 1)
  if (node_number < all_nodes - 1) {
    //fprintf(stderr, "Czekam na dwa inty od node'a %d\n", all_nodes-1);
    Receive(all_nodes - 1);
    lower_disc_section = GetInt(all_nodes - 1);
    upper_disc_section = GetInt(all_nodes - 1);
  }

  // obliczanie wyniku dla sekcji krytycznych
  
  LL blocked_disc_index = 0;
  LL blocked_disc_position = 3000000000000000000;
  lower_disc_i = lower_disc_index(lower_disc_section);
  upper_disc_i = upper_disc_index(upper_disc_section);
  ////fprintf(stderr, "Jest nodeów: %d\n", all_nodes);
  ////fprintf(stderr, "Bede pytal o dyski %lld-%lld z sekcji; %lld-%lld\n", lower_disc_i, upper_disc_i, lower_disc_section,
  //upper_disc_section);
  LL current_disc_i = lower_disc_i;
  
  ////fprintf(stderr, "Pytam o current_disc %lld, m=%lld\n", current_disc_i, m);
  LL current_disc_diameter = DiscDiameter(current_disc_i);
  LL current_hole_diameter = hole_diameters[lower_hole_i - upper_hole_i];
  for(LL i = lower_hole_i; i >= upper_hole_i; --i) {
    // to chyba moze nawalac przez 2 miliony maks
    while (current_disc_diameter <= current_hole_diameter && current_disc_i < upper_disc_i) {
      ++current_disc_i;
      ////fprintf(stderr, "Pytam o current_disc %lld, m=%lld\n", current_disc_i, m);
      current_disc_diameter = DiscDiameter(current_disc_i);
    }
    if (current_disc_diameter <= current_hole_diameter) {
      break;
    }
    // aktualny krazek nie zmiesci sie juz w i-tej dziurze lub przejrzano wszystkie krazki
    
    // podróż po dziurach aż do spotkania tej, na której zatrzymał się current_disc_i
    while (i > upper_hole_i) {
      --i;
      current_hole_diameter = hole_diameters[i - upper_hole_i];
     //fprintf(stderr, "Przechodze przez dziure %lld o srednicy %lld\n", i, current_hole_diameter);
      if (current_disc_diameter <= current_hole_diameter) {
        // znaleziono otwór, na którym się zablokuje
       //fprintf(stderr, "Dysk o indeksie %lld i średnicy %lld blokuje się w dziurze %lld o średnicy %lld\n",
        //current_disc_i, current_disc_diameter, i, current_hole_diameter);
        if(i < (blocked_disc_position - (current_disc_i - blocked_disc_index))) {
          blocked_disc_position = i;
          blocked_disc_index = current_disc_i;
        }
        break;
      }
    }
  }
 //fprintf(stderr, "Znalazlem krytyczny bloczek: %lld w dziurze %lld\n", blocked_disc_index, blocked_disc_position);
  // powinnismy teraz znac indeks i pozycje dysku z tego segmentu, ktory wplywa na to,
  // gdzie zablokowala sie sklejka dyskow z tego segmentu
  // blocked_disc_position - pozycja dziury (od góry) na której wisi krazek
  // blocked_disc_index - indeks dysku, ktory sie zablokowal (potrzebny do dodania pozniej
  // reszty dyskow, by zobaczyc czy to nie on jest najwczesniej blokujacym dyskiem

  // odebranie wyniku od niższej instancji lub nie jeśli najniższa instancja
  LL lower_section_blocked_disc_position=n+1, lower_section_blocked_disc_index=0;
  if (node_number < all_nodes - 1) {
    // odbierz wynik od niższej
    Receive(node_number+1);
    lower_section_blocked_disc_position = GetLL(node_number+1);
    lower_section_blocked_disc_index = GetLL(node_number+1);
  }
  // sprawdź, czy ten niżej nie blokuje bardziej niż twój
  if ( blocked_disc_index - lower_section_blocked_disc_index > lower_section_blocked_disc_position -
    blocked_disc_position) {
    // yup, psuje bardziej
    blocked_disc_index = lower_section_blocked_disc_index;
    blocked_disc_position = lower_section_blocked_disc_position;
  }

  // wysłanie wyniku instancji wyżej lub jej wypisanie
  if (node_number > 0) {
    // wyślij temu wyżej
    PutLL(node_number-1, blocked_disc_position);
    PutLL(node_number-1, blocked_disc_index);
    Send(node_number-1);
  } else {
    // jesteś tym najwyżej
    // wypisz wynik
    printf("%lld\n", MAX(0, blocked_disc_position - (m - blocked_disc_index)));
  }

  return EXIT_SUCCESS;
}