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
#include <iostream>
#include <cstdlib>
#include "krazki.h"
#include "message.h"
using namespace std;

int main()
{
    int n, m;
    n = PipeHeight();
    m = NumberOfDiscs();
    int st, nd;
    int my_id = MyNodeId() + 1;
    int nodes = NumberOfNodes();

    if(my_id == 1)
        st = 0;
    else
        st = (n/nodes) * (my_id - 1);

    if(my_id == nodes)
        nd = n;
    else
        nd = (n/nodes) * (my_id);
    int bottom = nd;
    if(st == nd) {
        bottom = n;
    }
    else {
        long long *pipe1 = new long long[nd - st + 10];
        int *pipe2 = new int[nd - st + 10];


        int d=0;
        long long smallest = 1000000000000000001L, x;
        for(int i=st+1; i<=nd; i++) {
            x = HoleDiameter(i);
            if(x<smallest) {
                pipe1[d]=x;
                pipe2[d++]=i;
                smallest=x;
            }
        }

        d--;
        int p, q;
        int bs;
        long long disc;
        for(int i=1; i<=m; i++) {
            disc = DiscDiameter(i);
            if(bottom == nd && disc <= pipe1[d]) {
                continue;
            }
            p = 0;
            q = d;
            int s;
            while(p<q) {
                s = (p + q) / 2;
                if(disc <= pipe1[s])
                    p = s + 1;
                else
                    q = s;
            }
            bs = q;
            if(bottom > pipe2[bs] - 1)
                bottom = pipe2[bs] - 1;
            else
                bottom--;

            if(bottom <= st) {
                bottom -= (m - i);
                break;
            }
        }
    }
    if(my_id != 1) {
        PutInt(0, bottom);
        Send(0);
        return 0;
    }

    int *bottoms = new int[nodes+2];
    for(int i=0; i<nodes; i++)
        bottoms[i] = -1;
    bottoms[0] = bottom;

    int actual = 0;
    int rec;
    int result;
    result = n + 1 - m;

    while(actual < nodes) {
        while(bottoms[actual] == -1) {
            rec = Receive(-1);
            bottom = GetInt(rec);
            bottoms[rec] = bottom;
        }
        if(actual == nodes-1)
            nd = n;
        else
            nd = (n/nodes) * (actual+1);
        if(bottoms[actual] > nd) {
            actual++;
            continue;
        }
        if(bottoms[actual] <= 0) {
            cout << 0 << '\n';
            return 0;
        }
        result = (result > bottoms[actual]) ? bottoms[actual] : result;
        actual++;
    }
    cout << result << '\n';

    return 0;
}