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

#include <iostream>

#define DEBUG_K(x)
#define DEBUG_M(x)
#define LOG_IF_M1   if (MyNodeId() == 0)
#define LOG_ID       DEBUG_M(cout << "{" << MyNodeId() << "} ";)

using namespace std;
#define Int     long long int

Int find_binary(Int *tab, Int target, Int begin, Int end) {
    DEBUG_K(LOG_ID
                    cout << begin << " " << end << " ";)

    if (begin > end)
        return end;

    if (target > tab[begin])
        return begin - 1;
    else if (target <= tab[end])
        return end;

    Int mid = begin;
    while (begin < end) {
        mid = (begin + end) / 2;
        if (tab[mid] > target) {
            if (end - begin == 1 && tab[end] < target) {
                break;
            } else {
                begin = mid;
            }
        } else if (tab[mid] < target) {
            end = mid;
        } else
            break;
    }

    while (mid < end) {
        if (tab[mid] == tab[mid + 1])
            ++mid;
        else
            break;
    }
    return mid;
}

int main() {
    DEBUG_M(LOG_IF_M1
                    cout << "START\n";)

    if (NumberOfDiscs() > PipeHeight()) {
        if (MyNodeId() == 0)
            cout << 0 << endl;
        return 0;
    }

    auto size = NumberOfDiscs() / NumberOfNodes();
    if (NumberOfDiscs() % NumberOfNodes() != 0)
        size += 1;
    auto discs_begin = size * MyNodeId();
    if (discs_begin >= NumberOfDiscs()) {
        DEBUG_M(LOG_ID
                        cout << "SUICIDE\n";)
        PutLL(0, 0);
        PutLL(0, 0);
        Send(0);
        return 0;
    }
    auto discs_end = discs_begin + size;
    discs_end = (discs_end <= NumberOfDiscs()) ? discs_end : NumberOfDiscs();

    constexpr Int begin = 0;
    Int end = PipeHeight();
    Int *tab = nullptr;

    if (PipeHeight() < 25000000 / sizeof(Int)) {
        ///////////////////////////////////////////////////////////////////////////////////////////
        tab = new Int[end - 1];
        Int current_fi_max = HoleDiameter(1);
        for (auto i = begin; i < end; ++i) {
            current_fi_max = min(HoleDiameter(i + 1), current_fi_max);
            tab[i] = current_fi_max;
            DEBUG_K(LOG_IF_M1
                            cout << tab[i] << " ";)
        }
        DEBUG_K(LOG_IF_M1
                        cout << "\n";)

        Int fi;
        for (auto i = discs_begin; i < discs_end; ++i) {
            fi = DiscDiameter(i + 1);
            end = find_binary(tab, fi, begin, end - 1);
            if (end < 0)
                break;
            DEBUG_K(cout << end << "\n";)
        }
        ////////////////////////////////////////////////////////////////////////////////////////////
    } else {
        ///////////////////////////////////////////////////////////////////////////////////////////
        Int fi;
        for (auto i = discs_begin; i < discs_end; ++i) {
            fi = DiscDiameter(i + 1);
            auto p = 1;
            while (p < end) {
                if (HoleDiameter(p) < fi)
                    break;
                ++p;
            }
            --p;
            if (end == 1 && p == 1) {
                end = -1;
                break;
            }
            end = p;
        }
        ///////////////////////////////////////////////////////////////////////////////////////////
    }

    if (MyNodeId() != 0) {
        DEBUG_M(LOG_ID
                        cout << "Sending\n";)
        PutLL(0, end);
        PutLL(0, size);
        Send(0);
    }

    // low due to optimization
    delete[] tab;
    if (MyNodeId() != 0)
        return 0;

    DEBUG_K(cout << 0 << "E = " << end << "\n";)
    Int iend, isize, icorrection;
    for (int i = 1; i < NumberOfNodes(); ++i) {
        DEBUG_M(LOG_ID
                        cout << "Gathering\n";)
        Receive(i);
        iend = GetLL(i);
        isize = GetLL(i);

        DEBUG_K(cout << i << "E = " << iend << " ";)

        if (isize) {
            if (iend < end) {
                icorrection = isize - end + iend;
                end = (icorrection > 0) ? iend - icorrection : iend;
            } else {
                end -= isize;
            };
            DEBUG_K(cout << end << "\n";)
        }
    }

    auto ans = end + 1;
    ans = (ans > 0) ? ans : 0;
    cout << ans << endl;
    return 0;
}