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

int first_of(int index, int n) {
	return std::min(index, 14) * n / 14;
}

template<class RandomIt1, class RandomIt2>
long long count_inversions(RandomIt1 first1, RandomIt1 last1, RandomIt2 first2, RandomIt2 last2) {
	long long result = 0;
	while (first1 != last1 && first2 != last2) {
		if (*first2 < *first1) {
			result += last1 - first1;
			++first2;
		} else {
			++first1;
		}
	}
	return result;
}

template<class RandomIt>
long long merge_sort(RandomIt first, RandomIt last) {
	long long result = 0;
	int size = last - first;
	if (size == 2) {
		RandomIt second = first;
		++second;
		result = *second < *first;
		if (result)
			std::iter_swap(first, second);
	} else if (size > 2) {
		RandomIt mid = first + size / 2;
		result += merge_sort(first, mid);
		result += merge_sort(mid, last);
		result += count_inversions(first, mid, mid, last);
		std::inplace_merge(first, mid, last);
	}
	return result;
}

int main() {
	int id = MyNodeId();
	long long result = 0;
	if (id == 0) {
		for (int i = 1; i < 100; i++) {
			int source = Receive(-1);
			result += GetLL(source);
		}
		std::cout << result;
	} else {
		int left_index = -id;
		int right_index = 0;
		while (left_index < 0) {
			right_index++;
			left_index += right_index;
		}
		int n = GetN();
		int left_first = first_of(left_index, n);
		int left_last = first_of(left_index + 1, n);
		int right_first = first_of(right_index, n);
		int right_last = first_of(right_index + 1, n);
		std::vector<int> left_array(left_last - left_first);
		std::vector<int> right_array(right_last - right_first);
		int i = left_first;
		for (auto&& e : left_array) {
			e = GetElement(i++);
		}
		i = right_first;
		for (auto&& e : right_array) {
			e = GetElement(i++);
		}
		if (right_index == left_index + 1)
			result = merge_sort(left_array.begin(), left_array.end());
		else
			std::sort(left_array.begin(), left_array.end());
		std::sort(right_array.begin(), right_array.end());
		result += count_inversions(left_array.begin(), left_array.end(), right_array.begin(), right_array.end());
		PutLL(0, result);
		Send(0);
	}
	return 0;
}