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

#include "krazki.h"
#include "message.h"
typedef long long ll;
/// maksymalna ilosc elementow na jeden node
const int MAX_SIZE = 25000000;
ll tab[MAX_SIZE + 9];
bool occupied[MAX_SIZE + 9];

void preprocess(int start, int end, int size) {
  /// uzyskuje ciag nierosnacy
  occupied[1] = false;
  tab[1] = HoleDiameter(start);
  // std::cerr << "hello i'm thread: " << start << " " << end << std::endl;
  // std::cerr << tab[1] << " ";
  for (int i = 2; i <= size; i++) {
    tab[i] = HoleDiameter(start + i - 1);
    if (tab[i] > tab[i - 1]) tab[i] = tab[i - 1];
    occupied[i] = false;
    // std::cerr << tab[i] << " ";
  }
  // std::cerr << std::endl;
}

void update(int value, int tab_size) {
  int current = 1;
  while (current <= tab_size && tab[current] > value) {
    tab[current] = value;
    current++;
  }
}

ll handle_requests(int *req_id, int total_req, int tab_size, int offset) {
  /// zdobadz przedzial do ktorego moze trafic aktualny element
  std::reverse(tab + 1, tab + tab_size + 1);
  std::reverse(occupied + 1, occupied + tab_size + 1);
  // for (int i = 1; i <= tab_size; i++) {
  //  std::cerr << tab[i] << " ";
  //}
  // std::cerr << std::endl;
  ll *start;
  ll *end;
  bool *position;
  int first;
  int last = 0;
  // std::cerr << "total requests: " << total_req << std::endl;
  while (true) {
    // std::cerr << "now in req: " << req_id << std::endl;
    if (*req_id > total_req) {
      std::cout << offset - 1 + (tab_size - first + 1) << std::endl;
      return -1;
    }
    ll disc = DiscDiameter(*req_id);
    // std::cerr << "disc is: " << disc << " last is: " << last << std::endl;
    if (tab[tab_size] < disc || occupied[tab_size]) {
      /// ten watek nie obsluzy tego dysku
      return disc;
    }
    start = std::lower_bound(tab + 1, tab + tab_size + 1, disc);
    first = std::max(int(start - tab), (last + 1));
    // std::cerr << "found range: " << first << " " << tab_size << std::endl;
    // start = std::upper_bound(tab + 1, tab + tab_size + 1, disc);
    if (start == tab + tab_size + 1) {
      return disc;
    }

    position = std::lower_bound(occupied + first, occupied + tab_size + 1, 0);
    if (position == occupied + tab_size + 1) {
      return disc;
    }
    // std::cerr << "put disc on pos: " << position - occupied << " "
    //          << tab_size - int(position - occupied) + 1 << std::endl;
    first = int(position - occupied);
    last = first;
    occupied[first] = true;
    (*req_id)++;
  }
}

int main() {
  int my_id = MyNodeId();
  int my_start = my_id * MAX_SIZE + 1;
  int total_h = PipeHeight();
  int my_end = std::min(my_start + MAX_SIZE - 1, total_h);
  int tab_size = my_end - my_start + 1;
  if (my_start > total_h) {
    return EXIT_SUCCESS;
  }
  preprocess(my_start, my_end, tab_size);

  int status;
  if (my_id != 0) {
    status = Receive(my_id - 1);
    ll min_so_far = GetLL(my_id - 1);
    update(min_so_far, tab_size);

    if (my_end < total_h) {
      PutLL(my_id + 1, tab[tab_size]);
      Send(my_id + 1);
    }

  } else if (my_id == 0 && my_end < total_h) {
    /// wyslij kolejnemu najmniejszego ktory sie zmiesci w czesci od 1 do my_end
    PutLL(1, tab[tab_size]);
    Send(1);
  }

  int total_req = NumberOfDiscs();
  int req_id = 1;
  /// jestesmy gotowi na odbieranie zapytan
  if (my_end != total_h) {
    /// poczekaj az ten przede mna caly sie zapelni
    status = Receive(my_id + 1);
    ll to_insert = GetLL(my_id + 1);
    if (to_insert == -1) {
      if (my_id == 0) {
        // std::cout << "c" << 0 << std::endl;
        return EXIT_SUCCESS;
      } else {
        PutLL(my_id - 1, to_insert);
        Send(my_id - 1);
        return EXIT_SUCCESS;
      }
    } else {
      req_id = GetInt(my_id + 1);
      // std::cerr << "zczynam ogarniac " << my_id << "\n";
      to_insert = handle_requests(&req_id, total_req, tab_size, my_start);
      if (my_id == 0 && to_insert != -1) {
        /// nie udalo sie wlozyc dysku, wypisz 0
        std::cout << 0 << std::endl;
        return EXIT_SUCCESS;
      } else if (my_id != 0) {
        /// dysk zatrzyma sie gdzies wczesniej
        PutLL(my_id - 1, to_insert);
        if (to_insert != -1) PutInt(my_id - 1, req_id);
        Send(my_id - 1);
      }
    }

  } else {
    /// funkcja handle_request zwroci wartosc krazka do wrzucenia albo -1 jesli
    /// obsluzono juz wszystkie
    // std::cerr << "zczynam ogarniac " << my_id << "\n";
    ll to_insert = handle_requests(&req_id, total_req, tab_size, my_start);
    // std::cerr << "skonczylem ogarniac\n";
    if (my_id == 0 && to_insert != -1) {
      /// nie udalo sie wlozyc dysku, wypisz 0
      std::cout << 0 << std::endl;
    } else if (my_id != 0) {
      /// dysk zatrzyma sie gdzies wczesniej
      PutLL(my_id - 1, to_insert);
      if (to_insert != -1) PutInt(my_id - 1, req_id);
      Send(my_id - 1);
    }
  }

  return EXIT_SUCCESS;
}