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

#include "krazki.h"
#include "message.h"

int main() {
    int n = PipeHeight();
    int m = NumberOfDiscs();
    std::vector<unsigned long long> hole_diamaters(n + 2, 0);
    hole_diamaters[n + 1] = (unsigned long long) -1;
    int top = 0;
    int segment_size = m/NumberOfNodes() + 1;
    int start = MyNodeId()*segment_size + 1;
    int end = MyNodeId()*segment_size + segment_size;

    if (end > m) {
        end = m;
    }

    int local_below = 0;
    int local_highest_floor = start > end ? 0 : 1;
    int local_above = end - start;

    for (int i = 1; i <= n; ++i) {
        unsigned long long r = HoleDiameter(i);
        if (r <= hole_diamaters[-i + n + 2]) {
            hole_diamaters[-i + n + 1] = r;
        } else {
            hole_diamaters[-i + n + 1] = hole_diamaters[-i + n + 2];
        }
    }

    for (int i = start; i <= end; ++i) {
        std::vector<unsigned long long>::iterator where = std::upper_bound(
            hole_diamaters.begin() + top + 1,
            hole_diamaters.end(),
            DiscDiameter(i) - 1
        );
        int candidate = int(where - hole_diamaters.begin());

        if (candidate - top > 1) {
            local_below = i - start;
            local_highest_floor = candidate;
            local_above = end - i;
        }
        top = candidate;
    }

    if (MyNodeId() != 0) {
        PutInt(0, local_below);
        PutInt(0, local_highest_floor);
        PutInt(0, local_above);
        Send(0);
    } else {
        for (int i = 1; i < NumberOfNodes(); ++i) {
            Receive(i);
            int below = GetInt(i);
            int highest_floor = GetInt(i);
            int above = GetInt(i);
            // printf("%d %d %d \n", below, highest_floor, top);
            if (highest_floor) {
                if (highest_floor <= top) {
                    top = top + below + above + 1;
                } else {
                    if (highest_floor - top - 1 >= below) {
                        top = highest_floor + above;
                    } else {
                        top = top + below + above - (highest_floor - top - 1) + 1;
                    }
                }
            }
        }
        printf("%d\n", top < n ? n - top + 1 : 0);
    }

    return EXIT_SUCCESS;
}