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
#include "message.h"
#include "teatr.h"
#include "bits/stdc++.h"
#include <cmath>
#include <cassert>

using namespace std;

typedef long long ll;

ll MAX_HEIGHT = 5;

// Finds the inversions number [beg, end] with assumption that the max height equals 5 and counts the sizes 
ll countInvAndHeights(ll beg, ll end, vector<ll>& H) {
    fill(H.begin(), H.end(), 0);
    ll inv = 0;
    for (ll i = beg; i <= end; ++i) {
        ll h = GetElement(i);
        for (ll j = h; j < MAX_HEIGHT; ++j) {
            inv += H[j];
        }
        H[h - 1] += 1; 
    }
    return inv;
}

ll countInvBasedOnHalfs(vector<ll>& l, vector<ll>& r) {
    ll inv = 0;
    for (ll i = 0; i < MAX_HEIGHT; ++i) {
        for (ll j = i + 1; j < MAX_HEIGHT; ++j) {
            inv += r[i] * l[j];
        }
    }
    return inv;
}

// Adds right to left vector.
void addHalfs(vector<ll>& l, vector<ll>& r) {
    for (ll i = 0; i < MAX_HEIGHT; ++i) {
        l[i] += r[i];
    }
}

int main() {
    ll id = MyNodeId();
    ll nodesNo = NumberOfNodes();
    ll n = GetN();
    if (id >= n) {
        return 0;
    }
    nodesNo = min(nodesNo, n);

    vector<ll> H(MAX_HEIGHT);
    ll len = (n + nodesNo - 1) / nodesNo;
    ll beg = id * len;
    ll end = min(beg + len - 1, n - 1);
    //cout << "My starting block is [" << beg << ", " << end << "]" << endl;
    ll inv = countInvAndHeights(beg, end, H);
    //cout << "inv number in my starting block: " << inv << endl;

    ll round = 2;
    while (id % round == 0 && round / 2 <= nodesNo) {
        // Get id of your brother
        ll brotherId = id + (round / 2);
        
        // If you have brother, then receive message from him
        if (brotherId < nodesNo) {
            ll sender = Receive(brotherId);
            vector<ll> HB(MAX_HEIGHT);
            for (ll i = 0; i < MAX_HEIGHT; ++i) {
                HB[i] = GetInt(brotherId);
            }
            inv += GetInt(brotherId);
            inv += countInvBasedOnHalfs(H, HB);
            addHalfs(H, HB);
        }
        round *= 2;
    }

    // I'm the boss 
    if (id == 0) {
        cout << inv << endl;
        return 0;
    }
    
    // if i'm not the boss, send my results to the guy on the left 
    ll brotherId = id - (round / 2);
    for (ll i = 0; i < MAX_HEIGHT; ++i) {
        PutInt(brotherId, H[i]);
    }
    PutInt(brotherId, inv);
    Send(brotherId);

    return 0;
}