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
#include "krazki.h"
#include "message.h"

#include <cstdio>
#include <algorithm>
#include <functional>

const int MAX_NODES = 100;
const int MAX_N = 200000000;
const int MAX_M = 200000000;
const int MAX_PART_N = 4000009;
const int MAX_PART_M = 4000009;
const long long INF = 1000LL*1000LL*1000LL*1000LL*1000LL*1000LL+9;

int id;
int nodes;

int n, m;

int tops[MAX_NODES+9];
long long mins[MAX_NODES+9];
long long pipe[3*MAX_PART_N+9];
long long discs[MAX_PART_M+9];

void sendto(int to, long long* a, int n) {
    for (int i = 0; i < n; ++i) {
        PutLL(to, a[i]);
    }
    Send(to);
}

void recvfrom(int from, long long* a, int n) {
    Receive(from);
    for (int i = 0; i < n; ++i) {
        a[i] = GetLL(from);
    }
}

long long compute_min_pipe() {
    long long min = INF;
    int b = (((long long)id)*n)/nodes+1;
    int e = std::min((long long)n+1, (((long long)id+1)*n)/nodes+2);
    for (int i = b; i < e; ++i) {
        long long d = HoleDiameter(i);
        min = std::min(min, d);
    }
    return min;
}

int compute_top_disc() {
    int b = (((long long)id)*m)/nodes+1;
    int e = (((long long)id+1)*m)/nodes+1;
    int min = nodes+1;
    for (int i = b; i < e; ++i) {
        long long d = discs[i-b] = DiscDiameter(i);
        long long* cur = std::upper_bound(mins, mins+nodes, d, std::greater<long long>());
        min = std::min((int)std::distance(mins, cur), min);
    }
    int pb = (((long long)min)*n)/nodes+1; 
    int pe = std::min((long long)n+1, (((long long)min+1)*n)/nodes+1+(e-b)+10);
    int pn = pe-pb;
    if (pb <= n) {
        pipe[0] = HoleDiameter(pb);
    }
    for (int i = pb+1; i < pe; ++i) {
        pipe[i-pb] = std::min(pipe[i-pb-1], HoleDiameter(i));
    }
    int top = pe;
    for (int i = b; i < e; ++i) {
        long long* cur = std::upper_bound(pipe, pipe+pn, discs[i-b], std::greater<long long>())-1;
        top = std::min(pb+(int)std::distance(pipe, cur), top-1);
    }
    top = std::min(top, pe-(e-b));
    return top;
}

int disc_num_for(int node) {
    return (((long long)node+1)*m)/nodes-(((long long)node)*m)/nodes;
}

int main() {
    id = MyNodeId();
    nodes = NumberOfNodes();
    n = PipeHeight();
    m = NumberOfDiscs();
    
    if (n < m) {
        if (id == 0) {
            puts("0");
        }
        return 0;
    }
    if (n < nodes) {
        nodes = n;
        if (id >= nodes) {
            return 0;
        }
    }
    
    long long min = compute_min_pipe();
    if (id == 0) {
        mins[0] = min;
    } else {
        PutLL(0, min);
        Send(0);
    }
    
    if (id == 0) {
        for (int i = 1; i < nodes; ++i) {
            int from = Receive(-1);
            long long val = GetLL(from);
            mins[from] = val;
        }
        for (int i = 1; i < nodes; ++i) {
            min = mins[i] = std::min(mins[i], min);
        }
        for (int i = 1; i < nodes; ++i) {
            sendto(i, mins, nodes);
        }
    } else {
        recvfrom(0, mins, nodes);
    }
    
    int top = compute_top_disc();
    if (id == 0) {
        tops[0] = top;
        for (int i = 1; i < nodes; ++i) {
            int from = Receive(-1);
            int val = GetInt(from);
            tops[from] = val;
        }
        for (int i = 1; i < nodes; ++i) {
            tops[i] = std::min(tops[i], tops[i-1]-disc_num_for(i));
        }
        if (tops[nodes-1] >= 0) {
            printf("%d\n", tops[nodes-1]);
        } else {
            puts("0");
        }
    } else {
        PutInt(0, top);
        Send(0);
    }
}