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
// Jedna instancja wypisuje maksymalny wzrost.

#include "message.h"
#include "teatr.h"
#include "bits/stdc++.h"
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;

template<class Iter, class Cmp = std::less<typename std::iterator_traits<Iter>::value_type>>
unsigned int merge(Iter begin, Iter mid, Iter end, const Cmp& cmp = Cmp())
{
    auto lhs_len = std::distance(begin,mid);
    unsigned int count = 0;
    
    // reserve space for sort-bed
    std::vector<typename std::iterator_traits<Iter>::value_type> sorted;
    
    Iter lhs = begin, rhs = mid;
    while (lhs != mid && rhs != end)
    {
        if (cmp(*lhs,*rhs) || !cmp(*rhs,*lhs))
            sorted.emplace_back(*lhs++);
        else
        {   // bump count with rhs moves
            sorted.emplace_back(*rhs++);
            count += (lhs_len - std::distance(begin,lhs));
        }
    }
    
    // finish missing segment
    while (lhs != mid)
        sorted.emplace_back(*lhs++);
    while (rhs != end)
        sorted.emplace_back(*rhs++);

    // move sorted data back into place
    std::copy(sorted.begin(), sorted.end(), begin);
    
    return count;
}

// mergesort algorithm
template<class Iter, class Cmp = std::less<typename std::iterator_traits<Iter>::value_type>>
unsigned int mergesort(Iter begin, Iter end, const Cmp& cmp = Cmp())
{
    auto len = std::distance(begin, end);
    if (len < 2)
        return 0;
    
    Iter mid = std::next(begin, len/2);
    
    return mergesort(begin, mid, cmp) +
           mergesort(mid, end, cmp) +
           merge(begin, mid, end, cmp);
}


int computeA(int n, int numberOfNodes, int myNodeId) {
	return round(((n* (myNodeId - 1)) / (numberOfNodes-1)));
}

int computeB(int n, int numberOfNodes, int myNodeId) {
	if (myNodeId == numberOfNodes-1) {
		return n-1;
	}
	return computeA(n, numberOfNodes, myNodeId + 1) - 1;
}

int main() {
  int myNodeId = MyNodeId();
  int numberOfNodes = NumberOfNodes();
  if(myNodeId != 0) {
  	int n = GetN();
  	int id = myNodeId - 1;
    int a = computeA(n, numberOfNodes, myNodeId);
    int b = computeB(n, numberOfNodes, myNodeId);
    if ( b < a) {
    	PutLL(0,0);
    	PutInt(0, -1);
    	Send(0);
    	return 0;
    }
    map<int, int> counts;
    vector<int> arr;
    for (int i=0; i<=b-a; i++) {
    	int h = GetElement(a + i);
    	if (counts.find(h) == counts.end()) {
    		counts[h] = 1;
    	} else {
    		counts[h] = counts[h] + 1;
    	}
    	arr.push_back(h);
   // 	cout << "read: " << i << " " << h << endl;
    }
    long long inverses = mergesort(arr.begin(), arr.end());
  //  cout << "inverses=" << inverses << endl;
    PutLL(0, inverses);
 // 	cout << "myNodeId: " << myNodeId << ", a="<<a<<", b="<<b << endl;
	for (auto it = counts.begin(); it != counts.end(); it++) {
		PutInt(0, it->first);
		PutInt(0, it->second);
	}
  	PutInt(0, -1);
  	Send(0);
  	return 0;
  }
//  cout << "my node id: " << MyNodeId() << endl;
  long long result = 0;
  map<int, map<int, int>> counts_per_instance;
  for(int i=0; i<numberOfNodes-1; i++) {
 // 	cout << "trying to receive new message" <<endl;
  	int instance = Receive(-1);
  	counts_per_instance[instance - 1] = map<int, int>();
//  	cout << "received from "<< instance << endl;
  	long long inner_conflicts = GetLL(instance);
  //	cout << "inner conflicts=" << inner_conflicts <<endl;
  	result += inner_conflicts;
  	int key = GetInt(instance);
//  	cout << "key=" << key <<endl;
  	while (key >= 0) {
  //		cout << "trying to receive new value" << endl;
  		long long value = GetInt(instance);
  		counts_per_instance[instance - 1][key] = value;
 // 		cout << "value=" << value <<endl;
  		key = GetInt(instance);
  	//	cout << "key=" << key <<endl;
  	}
  }
  for(int i=0; i<numberOfNodes-2; i++) {
  	for (int j=i+1; j<numberOfNodes-1; j++) {
  	//	cout << "i=" << i << ", j=" << j << endl;
  		map<int, int> counts_i = counts_per_instance[i];
  		map<int, int> counts_j = counts_per_instance[j];
  		for (auto it_i = counts_i.begin(); it_i != counts_i.end(); it_i ++) {
  			for (auto it_j = counts_j.begin(); it_j != counts_j.end(); it_j++) {
  				int h1 = it_i->first;
  				int c1 = it_i->second;
  				int h2 = it_j->first;
  				int c2 = it_j->second;
  	//			cout << "h1=" << h1 << ", c1=" << c1 << ", h2= " << h2<< ". c2="<< c2 <<endl;
  				if (h1 > h2) {
  //					cout << "found conflicts=" << c1*c2 << endl;
  					result += c1*c2;
  				}
  			}
  		}
  	}
  }
  cout << result << "\n";
  return 0;
}