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

#include <iostream>
#include <sstream>

int main() 
{
    //FILE * log_file;
    //char name[100];
    //sprintf(name, "/tmp/kra_log_%d.txt", MyNodeId());
    //log_file = fopen(name, "w");

    int n = PipeHeight();
    int m = NumberOfDiscs();
    int number_of_nodes = NumberOfNodes();
    int my_node_id = MyNodeId();

    int part = std::max(2, (n / number_of_nodes) + 1); //TEST
    int n_parts = std::ceil(float(n) / part);

    //fprintf(log_file, "id: %d: part:%d n_parts:%d\n", my_node_id, part, n_parts);

    if (my_node_id >= n_parts) {
        //fprintf(log_file, "node_id > n_parts\n");
        //fclose(log_file);
        return 0;
    }

    bool is_last_node = (n_parts - 1 == my_node_id);
    bool is_first_node = (my_node_id == 0);

    if (m > n) {
        if (is_first_node)
            printf("0\n");
        //fprintf(log_file, "m > n\n");
        //fclose(log_file);
        return 0;
    }

    int n_start = part * my_node_id + 1;
    int n_end   = std::min(n_start + part - 1, n);

    part = n_end - n_start + 1;

    //fprintf(log_file, "id: %d: part:%d range: %d %d, is_last %d \n", my_node_id, part, n_start, n_end, is_last_node);

    long long pipe[part + 1];
    pipe[0] = 1000000000000000000;
    if (!is_first_node) {
        Receive(my_node_id - 1);
        pipe[0] = GetLL(my_node_id - 1);
        //fprintf(log_file, "got prev pipa size %d\n", pipe[0]);
    }


    //fprintf(log_file, "pipe: ");
    for (int i = 1; i <= part; ++i) {
        pipe[i] = std::min(pipe[i-1], HoleDiameter(i + n_start - 1));
        //fprintf(log_file, "%d ", pipe[i]);
    }
    //fprintf(log_file, "%d");

    if (!is_last_node)
    {
        //fprintf(log_file, "send last pipe size %d\n", pipe[part]);
        PutLL(my_node_id + 1, pipe[part]);
        Send(my_node_id + 1);
    }

    //fprintf(log_file, "%d start sorting\n", my_node_id);

    int j = 1;
    int i = part;
    if (!is_last_node) {
        Receive(my_node_id + 1);
        j = GetInt(my_node_id + 1);

        //fprintf(log_file, "got j:%d\n", j);

        if (j > m) {
            //fprintf(log_file, "EXIT nothing to do\n");
            //fclose(log_file);
            return 0;
        }
    }

    while (j <= m && i >= 1)
    {
        //fprintf(log_file, "try insert disc: %d (%d) in pipe: %d (%d)\n", j, DiscDiameter(j), i, pipe[i]); 
        if (pipe[i] >= DiscDiameter(j)) {
            //fprintf(log_file, "insert disc: %d (%d) in pipe: %d (%d)\n", j, DiscDiameter(j), i, pipe[i]); 
            ++j;
        }
        --i;
    }

    if (j > m)
        printf("%d\n", std::max(0, n_start + i - (m-j+1)));
    else if (is_first_node) {
        printf("0\n");
    }

    if (!is_first_node) {
        PutInt(my_node_id - 1, j);
        Send(my_node_id - 1);

        //fprintf(log_file, "send j:%d\n", j);
    }

    //fprintf(log_file, "EXIT normal\n");
    //fclose(log_file);

    return 0;
}