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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include "message.h"
#include "teatr.h"

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

static const int COORDINATOR_NODE_ID = 0;

std::vector<int> mergeVec;

long long merge(
	int *tab,
	int leftStart,
	const int leftEnd,
	int rightStart,
	const int rightEnd
)
{
	assert(leftEnd >= leftStart);
	assert(rightEnd >= rightStart);
	assert(leftEnd == rightStart);

	long long result = 0;

	mergeVec.clear();
	const int origStart = leftStart;

	while (leftEnd - leftStart > 0 || rightEnd - rightStart > 0) {
		if (leftEnd - leftStart > 0 && rightEnd - rightStart > 0) {
			if (tab[leftStart] <= tab[rightStart]) {
				// take left
				mergeVec.push_back(tab[leftStart++]);
			} else {
				// take right
				mergeVec.push_back(tab[rightStart++]);
				result += leftEnd - leftStart;
			}
		} else if (leftEnd - leftStart > 0) {
			// take left
			mergeVec.push_back(tab[leftStart++]);
		} else {
			assert(rightEnd - rightStart > 0);
			assert(leftEnd == leftStart);
			// take right
			mergeVec.push_back(tab[rightStart++]);
		}
	}

	for (int i = 0; i < (int)mergeVec.size(); ++i)
		tab[origStart + i] = mergeVec[i];

	return result;
}

long long doMergeSort(int *tab, const int start, const int end)
{
	assert(end >= start);

	if (end - start <= 1)
		return 0;

	const int middle = (start + end) / 2;
	
	const long long leftResult = doMergeSort(tab, start, middle);
	const long long rightResult = doMergeSort(tab, middle, end);
	const long long mergeResult = merge(tab, start, middle, middle, end);

	return leftResult + rightResult + mergeResult;
}

long long mergeSort(std::vector<int> &vec)
{
	return doMergeSort(&vec.front(), 0, (int)vec.size());
}

std::ostream &operator<<(std::ostream &out, const std::vector<int> &vec)
{
	for (int i = 0; i < (int)vec.size(); ++i)
		out << vec[i] << ' ';
	return out;
}

void testMergeSort()
{
	int n;
	std::cin >> n;
	std::vector<int> testVec(n);
	for (int i = 0; i < n; ++i)
		std::cin >> testVec[i];
	long long testResult = mergeSort(testVec);
	std::cout << "testResult=" << testResult << "\nsorted: " << testVec << std::endl;
}

int main()
{
	//testMergeSort();
	//return 0;

	const int nodeId = MyNodeId();
	const int numberOfNodes = NumberOfNodes();

	const int N = GetN();
	const int middle = N / 2;

	// Each worker computes 1/numWorkers of elements of first half (call it X) and second half such that no pair with
	// both ends in X is included. They send result to coordinator. Coordinator decreases it by elements from the second
	// half. When all workers results are summed up, this is result for pairs between first half and second half.
	// Coordinator computes for first half and second half and adds these 2 values to the sum from workers.

	const int numWorkers = std::min(middle, numberOfNodes - 1);
	std::vector<int> buf;

	if (nodeId == COORDINATOR_NODE_ID) {
		// first half
		buf.resize(middle);
		for (int i = 0; i < middle; ++i)
			buf[i] = GetElement(i);
		const long long firstHalfResult = mergeSort(buf);

		// second half
		buf.resize(N - middle);
		for (int i = 0; i < N - middle; ++i)
			buf[i] = GetElement(middle + i);
		const long long secondHalfResult = mergeSort(buf);

		long long workersResult = 0;
		for (int i = 0; i < numWorkers; ++i) {
			const int workerNodeId = Receive(-1);
			const long long partialResult = GetLL(workerNodeId);
			workersResult += partialResult - secondHalfResult;
		}

		const long long finalResult = firstHalfResult + secondHalfResult + workersResult;
		std::cout << finalResult << std::endl;
	} else if (nodeId <= numWorkers) {
		// useful worker
		const int firstHalfElemsPerWorkerFloor = middle / numWorkers;
		assert(firstHalfElemsPerWorkerFloor >= 1);

		const int startOfElemsInFirstHalf = (nodeId - 1) * firstHalfElemsPerWorkerFloor;
		const int elemsInFirstHalf = nodeId < numWorkers ? firstHalfElemsPerWorkerFloor :
			(firstHalfElemsPerWorkerFloor + middle % numWorkers);

		// first compute for first half
		buf.resize(elemsInFirstHalf);
		for (int i = 0; i < elemsInFirstHalf; ++i)
			buf[i] = GetElement(startOfElemsInFirstHalf + i);
		const long long fhResult = mergeSort(buf);

		// second, add remaining from second half and compute
		buf.resize(elemsInFirstHalf + N - middle);
		for (int i = 0; i < N - middle; ++i)
			buf[elemsInFirstHalf + i] = GetElement(middle + i);
		const long long fhAndShResult = mergeSort(buf);

		const long long partialResult = fhAndShResult - fhResult;
		PutLL(COORDINATOR_NODE_ID, partialResult);
		Send(COORDINATOR_NODE_ID);
	}
	return 0;
}