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

#define T_SIZE 1000001

int TAB[T_SIZE];
int MAX_H = 1;

void mb_read_msg(int src) {
    TAB[0] += GetInt(src);
    int m = GetInt(src);
    int h, hc;
    while (m > 0) {
        h = GetInt(src);
        hc = GetInt(src);
        for (int i = h + 1; i < T_SIZE && i < MAX_H; ++i) {
            TAB[0] += hc * TAB[i];
        }
        TAB[h] += hc;
        if (h > MAX_H) {
            MAX_H = h;
        }
        --m;
    }
}

int main() {
    const int N = GetN();
    const int ID = MyNodeId();
    const int INSTANCES = NumberOfNodes();

    int PART_SIZE;
    int END;

    int elem_i = 0, elem_k = 0;
    int counter = 0;

    for (int i = 0; i < T_SIZE; ++i) {
        TAB[i] = 0;
    }

    if (N % INSTANCES == 0) {
        PART_SIZE = N / INSTANCES;
    } else {
        PART_SIZE = N / INSTANCES + 1;
    }

    END = (ID + 1) * PART_SIZE;

    for (int i = ID * PART_SIZE; i < N && i < END; ++i) {
        elem_i = GetElement(i);
        if (TAB[elem_i] == 0) {
            ++counter;
        }
        ++TAB[elem_i];
        if (elem_i > MAX_H) {
            MAX_H = elem_i;
        }

        for (int k = i + 1; k < N && k < END; ++k) {
            elem_k = GetElement(k);
            if (elem_k < elem_i) {
                ++TAB[0];
            }
        }
    }

    if (ID == 0) {
        for (int i = 1; i < INSTANCES; ++i) {
            Receive(i);
            mb_read_msg(i);
        }
        std::cout << TAB[0];
    } else {
        PutInt(0, TAB[0]);
        PutInt(0, counter);
        for (int i = 1; counter > 0 && i < T_SIZE; ++i) {
            if (TAB[i] > 0) {
                PutInt(0, i);
                PutInt(0, TAB[i]);
                --counter;
            }
        }
        Send(0);
    }

    return 0;
}