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

using namespace std;

int main()
{
    int n, m, przedzial, wezly, moj_numer;
    int start, koniec;
    int minimum = 0;

    n = PipeHeight();
    m = NumberOfDiscs();
    wezly = NumberOfNodes();
    moj_numer = MyNodeId();

    if (n < m)
    {
        if (moj_numer == 0)
            printf("0");
        return 0;
    }

    if (n < wezly && moj_numer != 0)
        return 0;

    start = moj_numer * (n / wezly);

    if (n < wezly)
        koniec = n - 1;
    else if (moj_numer == wezly - 1)
        koniec = n - 1;
    else
        koniec = start + n / wezly - 1;
    
    przedzial = koniec - start + 1;

    //printf("[%d, %d] (%d)\n", start, koniec, przedzial);
    
    long long int poprz, akt;
    vector<long long int> walce(przedzial);
    poprz = HoleDiameter(start + 1);
    walce[0] = poprz;
    minimum = poprz;
    //printf("[1] = %d\n", poprz);    
    for(int i = 1; i < przedzial; ++i)
    {
        akt = HoleDiameter(start + i + 1);
        //printf("[%d] = %d\n", start + i + 1, akt);
        if (akt < poprz)
            poprz = akt;
        walce[i] = poprz;
    }

    //printf("MIN: %d\n", poprz);

    
    if (moj_numer > 0) // oczekuj na minimum od wyzszych 
    {
        Receive(moj_numer - 1);
        minimum = GetLL(moj_numer - 1);
    }
    if (koniec != n - 1) // poinformuj nizszy o minimach
    {
        PutLL(moj_numer + 1, minimum < poprz ? minimum : poprz);
        Send(moj_numer + 1);
    }
    //printf("Min: %d\n", minimum);
    

    /*if (moj_numer == 1)
    return 0;*/
    int ost_krazek = 1;
    if (koniec != n - 1) // oczekuj na informacje od nizszej o pierwszym niedopasowanym krazku
    {
        poprz = Receive(moj_numer + 1);
        //printf("Czytam od %d \n", poprz);

        ost_krazek = GetInt(moj_numer + 1);
        //printf("Odebralem: %d\n", ost_krazek);

        if (ost_krazek < 0)
        {
            if (moj_numer == 0)
            {
                printf("%d", ost_krazek * (-1));
            }
            else
            {
                PutInt(moj_numer - 1, ost_krazek);
                Send(moj_numer - 1);
            }
            return 0;
        }
    }
    
    int przesuniecie = 0;
    bool dopasowano;
    while (przesuniecie < przedzial && ost_krazek + przesuniecie <= m)
    {
        akt = DiscDiameter(ost_krazek + przesuniecie);
        //printf("Proboje dopasowac: [%d] = %d\n", ost_krazek + przesuniecie, akt);
        dopasowano = false;
        while(start <= koniec && !dopasowano)
        {
            //printf("Porownoje: %d vs. [%d =:: %d] = %d\n", akt, koniec-start, koniec + 1, (minimum < walce[koniec - start] ? minimum : walce[koniec - start]));
            if (akt <= (minimum < walce[koniec - start] ? minimum : walce[koniec - start]))
            {
                dopasowano = true;
            }
            koniec--;
        }

        if (!dopasowano)
            break;
        przesuniecie++;
    }

    //printf("Po petli: %d, poz. \n", ost_krazek + przesuniecie);

    if (moj_numer > 0) // Wyslij wyzej numer krazka, od ktorego ma zaczac
    {
        if (!dopasowano)
            PutInt(moj_numer - 1, ost_krazek + przesuniecie);
        else if (ost_krazek + przesuniecie > m) // Zmieszczone w calosci
            PutInt(moj_numer - 1, (koniec + 1 + 1) * (-1));
        else // dopasowano
            PutInt(moj_numer - 1, ost_krazek + przesuniecie);
        Send(moj_numer - 1);
        //printf("==> Send %d", moj_numer - 1);
    }
    else
    {
        if (!dopasowano)
            printf("0");
        else
            printf("%d", koniec - start + 1 + 1);
    }

}