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
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
#include <iostream>
#include "message.h"
#include "krazki.h"
#include <limits>       // std::numeric_limits

using namespace std;

long long pipe[30000000];
long long pipesLenght[100];
long long pipeStartWidth[100];
long long pipeEndWidth[100];
long long discStartWidth[100];
long long discEndWidth[100];
long long firstOutsideDisc[100];
long long emptyPipeBlock[100];//ilosc pustych bloków przed najwy¿szym dyskiem, od do³u fragmentu pipa
long long highestdisckPosition[100]; //pozycja najwyzszego dysku w danym fragmencie pipa (ujemna oznacza ¿e wyszliœmy z dysku, 0 -> jesteœmy na lini pipa)

int main()
{
   long long instanceCount = NumberOfNodes();
   const long long instanceId = MyNodeId();
   const long long pipeHeight = PipeHeight();
   const long long discNo = NumberOfDiscs();

   if(discNo > pipeHeight)
   {
      if(instanceId == 0)
         cout<<0;
      return 0;
   }

   if(instanceCount > pipeHeight)
      instanceCount = pipeHeight;
   if(pipeHeight > discNo)
      instanceCount = discNo;

   if(instanceId >= instanceCount)
      return 0;

   long long pipeStart;
   long long pipeEnd;
   long long pipeLenght;

   long long discStart; //pierwszy dysk tej instancji
   long long discEnd; //pierwszy dysk nastepnej instancji
   long long discLenght;

   long long* discs;

//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   {
      pipeStart = 1 + (instanceId * pipeHeight) / instanceCount;
      pipeEnd = 1 + ((instanceId + 1) * pipeHeight) / instanceCount;
      pipeLenght = pipeEnd - pipeStart;

      discStart = 1 + (instanceId * discNo) / instanceCount; //pierwszy dysk tej instancji
      discEnd = 1 + ((instanceId + 1) * discNo) / instanceCount; //pierwszy dysk nastepnej instancji
      discLenght = discEnd - discStart;

      discs = pipe + pipeLenght;
   }

   //czytamy dyski i obudowywujemy

//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   {
      long long max = 0;
      for(int i = 0; i < discLenght; i++)
      {
         long long curr = DiscDiameter(i + discStart);
         if(curr > max)
            max = curr;

         discs[i] = max;
      }
   }

   //czytamy rurke i obcinamy
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   {
      long long min = std::numeric_limits<long long>::max();
      for(int i = pipeLenght - 1 ; i >= 0; i--)
      {
         long long curr = HoleDiameter(pipeHeight - (i + pipeStart) + 1);
         if(curr < min)
            min = curr;

         pipe[i] = min;
      }
   }

   //obliczamy poczatkowy i koncowa szerokosc rurki
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   {
      long long pipemin = pipe[0];
      long long pipemax = pipe[pipeLenght - 1];
      long long discmin = discs[0];
      long long discmax = discs[discLenght - 1];

      // i wysylamy do instancji 0
      PutLL(0, pipeLenght);
      PutLL(0, pipemin);
      PutLL(0, pipemax);
      PutLL(0, discmin);
      PutLL(0, discmax);
      Send(0);
   }

   //instancja 0 odbiór i wyslanie do pozosta³y o przyciêcie krazków i rurki
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   if(instanceId == 0)
   {
      for(int i = 0; i < instanceCount; i++)
      {
         int node = Receive(-1);
         pipesLenght[node] = GetLL(node);
         pipeStartWidth[node] = GetLL(node);
         pipeEndWidth[node] = GetLL(node);
         discStartWidth[node] = GetLL(node);
         discEndWidth[node] = GetLL(node);
      }

      //rozszerzenie krazków
      long long max_disc = 0;
      for(int i = 0; i < instanceCount; i++)
      {
         if(discStartWidth[i] < max_disc)
            discStartWidth[i] = max_disc;

         PutLL(i, max_disc);
         Send(i);
         if(max_disc < discEndWidth[i])
            max_disc = discEndWidth[i];

         discEndWidth[i] = max_disc;
      }

      //zwezanie rurki
      long long min_pipe = std::numeric_limits<long long>::max();
      for(int i = instanceCount - 1; i >= 0; i--)
      {
         if(pipeEndWidth[i] == 0)
         {
            pipeEndWidth[i] = min_pipe;
            pipeStartWidth[i] = min_pipe;
         }

         if(pipeEndWidth[i] > min_pipe)
            pipeEndWidth[i] = min_pipe;

         PutLL(i, min_pipe);
         Send(i);
         if(min_pipe > pipeStartWidth[i])
            min_pipe = pipeStartWidth[i];

         pipeStartWidth[i] = min_pipe;
      }
   }

   //odbor informacji o minimalnej szerokości krażków
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   {
      Receive(0);
      long long min_disc = GetLL(0);
      for(int i = 0; i < discLenght && discs[i] < min_disc; i++)
      {
         discs[i] = min_disc;
      }
   }
   //odbor informacji o maxymalnej szerokości rurki
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   {
      Receive(0);
      long long max_pipe = GetLL(0);
      for(int i = pipeLenght - 1; i >= 0 && pipe[i] > max_pipe; i++)
      {
         pipe[i] = max_pipe;
      }
   }

   //instancja 0 wysy³a zapytania do innych instancji o przedzia³y kr¹¿ków. Kiedy zakoñczy wysy³a do wszystkich liczbê -1
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   if(instanceId == 0)
   {
      //szukamy który krązek jako pierwszy się nie zmieści
      //pierwszy szerszy od góry rurki (czyli szerszy od pipeEndWidth)
      int j = 0;
      for(int i = 0; i < instanceCount; i++)
      {
         int FirstDiscOutsideWidth = pipeEndWidth[i] + 1;//jak ma sie nie zmiescic to musi byc przynajmniej o 1 szersza
         //szukamy która instancja ma ta infromacje
         for( ; j < instanceCount; j++)
         {
            if(discEndWidth[j] >= FirstDiscOutsideWidth)//znaleźlismy instancje która go ma, wysylamy do niej pytanie i przerywamy
            {
               PutLL(j, i);
               PutLL(j, FirstDiscOutsideWidth);
               Send(j);
               break;
            }

            //jeśli w tym nodzie nie ma tego przedzialu to w nastepnych tez go nie ma. Wysylamy mu info ze moze zakończyć szukanie i prześc dalej
            PutLL(j, -1);
            Send(j);
         }
         if(j == instanceCount) //nie wyslalismy informacji do żadnego noda, bo nody sie skończyły
         {
            //wysylamy żadanie do samej siebie z danymi
            PutLL(0, i);
            PutLL(0, discNo + 1);
            Send(0);
         }
      }
      for( ; j < instanceCount; j++) //wysylamy zadnie zakonczenia do pozostalych nodów
      {
         PutLL(j, -1);
         Send(j);
      }
   }

   //wszystkie odbieraj¹ monity o przedzia³y do otrzymania wartoœci -1;
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   {
      long long searchposition = 0;
      while(true)
      {
         Receive(0);
         long long node = GetLL(0);
         if(node == -1)
            break;
         long long discSize = GetLL(0);


         for(; searchposition < discLenght && discs[searchposition] < discSize; searchposition++)
         {
         }

         PutLL(0, node);
         PutLL(0, discStart + searchposition);
         Send(0);
      }
   }

   //node 0 odbiera wyniki od pozostalych nodów o przedzialach
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   if(instanceId == 0)
   {
      for(int i = 0; i < instanceCount; i++)
      {
         int node = Receive(-1);
         long long instnce = GetLL(node);
         firstOutsideDisc[instnce] = GetLL(node);
      }

      //poprawiamy przedzialy tak żeby nie były dłuższe nić wysokość fragmentu rurki
      int first = 1;
      for(int i = 0; i < instanceCount; i++)
      {
         if(firstOutsideDisc[i] - first > pipesLenght[i])
            firstOutsideDisc[i] = first + pipesLenght[i];

         first = firstOutsideDisc[i];
      }
   }

   //instancja 0 wysy³a do wszystkich monit o nowych przedzia³ach kr¹¿ków
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   if(instanceId == 0)
   {
      long long first = 1;
      for(int i = 0; i < instanceCount; i++)
      {
         PutLL(i, first);
         PutLL(i, firstOutsideDisc[i]);
         Send(i);
         first = firstOutsideDisc[i];
      }
   }

   //wszytskie instancje odbieraj¹ nowe przedzia³y kr¹¿ków, i dla nich obliczaj¹ gdzie kr¹¿ek siê skoñczy i ile by³o pustych pól

//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   {
      Receive(0);
      long long first = GetLL(0);
      long long firstOutside = GetLL(0);

      int pipePosition = 0;
      int emptyspaces = 0;
      while(first < firstOutside)
      {
         long long discdiam = DiscDiameter(first);
         for(; pipePosition < pipeLenght && pipe[pipePosition] < discdiam; pipePosition++)
         {
            emptyspaces++;
         }
         //we place disc on pipePosition, so nex we will start from pipePosition++
         pipePosition++;
         first++;
      }

      //wysylamy wynik
      PutLL(0, emptyspaces);
      PutLL(0, pipeLenght - pipePosition);
      Send(0);
   }

   //instancja 0 odbiera od wszytskich instancji informacje gdzie kr¹zki dosz³y i ile pustych pól mialy po drodze
//   for(int instanceId = 0; instanceId < instanceCount; instanceId++)
   if(instanceId == 0)
   {
      for(int i = 0; i < instanceCount; i++)
      {
         int node = Receive(-1);
         emptyPipeBlock[node] = GetLL(node);
         highestdisckPosition[node] = GetLL(node);
      }

      //instancja 0 oblicza ostateczny wynik:
      //    1. petla po instancjach od 0 do ostatniej instancji.
      //       1a. jezeli poprzednia instancja nie zmieœci³a siê w rurce AND iloœc wolnych przestrzani (w obecjen) jest mniejsza, ni¿ iloœæ wystaj¹ych z poprzedniej, obliczamy nowa pozycjê ostatniego krazka w obecnej instancji
      //          1aa. Nowa pozycja = stara pozycja + iloœc wystaj¹ych - iloœc wolnych przestrzeni
      for(int i = 0; i < instanceCount - 1; i++)
      {
         if(highestdisckPosition[i] < 0)//krazki wystają// musimy przesunac w gore nastepne// w górę znaczy dodaj to co wystaje
         {
            highestdisckPosition[i + 1] += highestdisckPosition[i] + emptyPipeBlock[i + 1]; //na 0 wystaje o -15, na jeden jest wgłąb na 10, pustych mamy 3, więc 10 += -15 + 3 = -2
         }
      }

      //maj¹c pozycje ostatniego krazka mo¿emy obliczyæ gdzie siê znajduje, pamiêtac musimy ¿e na równo w naszym kodzie oznacza liczbe 0, a mamy zwróciæ w takim wypadku liczbe 1. Wiêc do ostatecznego wyniku musimy dodaæ 1.
      int total = 0;
      for(int i = instanceCount - 1; i >= 0; i--)
      {
         if(highestdisckPosition[i] != pipesLenght[i])
         {
            total += highestdisckPosition[i];
            break;
         }
         total += pipesLenght[i];
      }
      //maj¹c pozycje ostatniego krazka mo¿emy obliczyæ gdzie siê znajduje, pamiêtac musimy ¿e na równo w naszym kodzie oznacza liczbe 0, a mamy zwróciæ w takim wypadku liczbe 1. Wiêc do ostatecznego wyniku musimy dodaæ 1.
      total++;

      //je¿li ostateczny wynik < 0, czyli wystaje z ostatniej rurki to wypisujemy 0, w przeciwnym wypadku wypisujemy wartoœæ.
      if(total < 0)
         total = 0;

      cout<<total;
   }

}