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
#include "message.h"
#include "krazki.h"
#include <cstdio>
#include <algorithm>
using namespace std;
#define MAXN 1000007
int n, m, current_batch, local_height;
long long kra[MAXN];
long long minima[207];
const int batch_size = 1000000;
int batches;

void read_batch(int id) {
  int start = id * batch_size;
  int ind = start;
  while(ind < n && ind < (id + 1) * batch_size) {
    int i = ind - start;
    kra[i] = HoleDiameter(1 + ind);
    if (i) {
      kra[i] = std::min(kra[i], kra[i-1]);
    } else if (id) {
      kra[i] = std::min(kra[i], minima[id-1]);
    }
    ind++;
  }
}

bool decrease_height() {
  if (local_height == 0) {
    //next batch
    if (current_batch == 0) {
      printf("0\n");
      return false;
    }
    current_batch--;
    read_batch(current_batch);
    local_height = batch_size;
  } else {
    local_height--;
  }
  return true;
}

bool process_next_disc(int id) {
  long long disc = DiscDiameter(id + 1);
//  printf("local height: %d, kra %lld\n", local_height, kra[local_height]);
  if (!decrease_height()) return false;
  while(disc > kra[local_height]) {
    if (!decrease_height()) return false;
  }
//  printf("finished\n");
  return true;
}

int main() {
  if (MyNodeId() != 0)
    return 0;
  n = PipeHeight();
  m = NumberOfDiscs();

  batches = (n + batch_size - 1)/ batch_size;
  //get minimal sizes of each batch of 10**6 size
  minima[0] = 1000000000LL * 1000000000LL + 1LL;
  for (int i = 0; i * batch_size < n; i++) {
    if (i) minima[i] = minima[i-1];
    for (int j = 0; j < batch_size; j++) {
      if (j + i * batch_size >= n)
        break;
      minima[i] = std::min(minima[i], HoleDiameter(1 + j + i * batch_size));
    }
  }

  current_batch = batches;
  if (n % batch_size == 0)
    local_height = batch_size;
  else
    local_height = n % batch_size;

  read_batch(current_batch);

  for(int i = 0; i < m; i++) {
    if (!process_next_disc(i))
      return 0;
  }
  printf("%d\n", local_height + 1 + current_batch * batch_size);
}