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

#define MAX_ELEM 5

using namespace std;

int main() {

	long long n = GetN();
	int nodes = NumberOfNodes();
	int myid = MyNodeId();

	long long from = (long long)myid * n / nodes;
	long long to = (long long)(myid + 1) * n / nodes;

	long long inversions = 0;

	long long sum[MAX_ELEM+1];
	for (int i = 0; i < MAX_ELEM + 1; i++)
		sum[i] = 0;

	for (long long i = from; i < to; i++)
	{
		int val = GetElement(i);
		sum[val]++;
		for (int j = val + 1; j <= MAX_ELEM; j++)
			inversions += sum[j];
	}

	PutLL(0, inversions);
	for (int j = 1; j <= MAX_ELEM; j++)
		PutLL(0, sum[j]);

	Send(0);

	if (myid == 0)
	{
		long long sumAll[MAX_ELEM + 1];
		for (int i = 0; i < MAX_ELEM + 1; i++)
			sumAll[i] = 0;

		long long result = 0;

		for (int i = 0; i < nodes; i++)
		{
			Receive(i);
			long long inversionsFromI = GetLL(i);
			result += inversionsFromI;

			for (int j = 1; j <= MAX_ELEM; j++)
			{
				long long receivedVal = GetLL(i);
				for (int k = j+1; k <= MAX_ELEM; k++)
					result += sumAll[k] * receivedVal;
				sumAll[j] += receivedVal;
			}
		}

		cout << result << endl;
	}
}