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

using ll = long long;
using namespace std;

const int const_max_element = 2*1024 - 4;
vector<int> numbers_list;
vector<int> numbers_list_indexes;
vector<int> max_element_list(const_max_element);
vector<int> counters_element_list(const_max_element);
ll conflict_counter = 0;

bool by_indexes(int i, int j) {
  return numbers_list[i] > numbers_list[j];
}

int main() {
  int node_id = MyNodeId();
  int number_of_nodes = NumberOfNodes();
  int n = GetN();
  int node_n_length = n / number_of_nodes + 1;
  if (n % number_of_nodes == 0)
    node_n_length = n / number_of_nodes;

  // cout << "node_id: " << node_id << endl;
  for (int i = node_id * node_n_length; i < (node_id + 1) * node_n_length; ++i) {
    // cout << "i: " << i << endl;
    if (i < n) {
      numbers_list.push_back(GetElement(i));
      // cout << numbers_list.back() << endl;
    }
  }
  for (int i = 0; i < numbers_list.size(); ++i)
    numbers_list_indexes.push_back(i);
  if (numbers_list_indexes.size() > 0) {
    sort(numbers_list_indexes.begin(), numbers_list_indexes.end(), by_indexes);
    // for (vector<int>::iterator it=numbers_list_indexes.begin(); it != numbers_list_indexes.end(); ++it)
    //   cout << "node_id: " << node_id << "numbers_list_indexes: " << *it << endl;
    int numbers_list_iterator = numbers_list_indexes.size()-1;
    // cout << "node_id: " << node_id << " numbers_list_iterator: " << numbers_list_iterator << endl;

    for (int i = 1; i < max_element_list.size(); ++i) {
      int current_number = numbers_list[numbers_list_indexes[numbers_list_iterator]];
      // cout << "node_id: " << node_id << " max_element_list: " << max_element_list.size() << endl;
      // cout << "i: " << i << " val: " << max_element_list[i] << endl;
      // cout << "it: " << numbers_list_iterator << endl;
      // cout << "numbers_list[numbers_list_indexes[it]]: " << current_number << endl;
      // cout << "---------------" << endl;
      if (i >= current_number) {
        int prev_number = current_number;
        int counter = 0;
        while (numbers_list_iterator >= 0 && current_number == prev_number) {
          numbers_list_iterator--;
          counter++;
          current_number = numbers_list[numbers_list_indexes[numbers_list_iterator]];
        }
        max_element_list[i] += counter;
      }
      max_element_list[i] += max_element_list[i-1];
      // cout << max_element_list[i] << endl;
      // cout << "numbers_list[numbers_list_indexes[it]]: " << current_number << endl;
      // cout << "node_id: " << node_id << endl;
    }
    for (int i = 0; i < numbers_list.size(); ++i) {
      counters_element_list[numbers_list[i]]++;
    }
    for (int i = 0; i < numbers_list.size() - 1; ++i) {
      for (int j = i; j < numbers_list.size(); ++j) {
        if (numbers_list[i] > numbers_list[j])
          conflict_counter++;
      }
    }
  }

  int range = 1;
  while (range <= number_of_nodes) {
    if (node_id % (range*2) != 0) {
      int receiver = node_id - range;

      for (int i = 1; i < max_element_list.size(); ++i) {
        PutInt(receiver, max_element_list[i]);
        if (i % 1024 == 0)
          Send(receiver);
      }
      Send(receiver);
      PutLL(receiver, conflict_counter);
      Send(receiver);
      // cout << "WYSYLAM do " << receiver << endl;
      return 0;
    } else {
      int sender = node_id + range;
      if (number_of_nodes > sender ) {
        vector<int> max_element_list_new(const_max_element);

        Receive(sender);
        for (int i = 1; i < max_element_list.size(); ++i) {
          max_element_list_new[i] = GetInt(sender);
          int how_many_elements = max_element_list[i] - max_element_list[i-1];
          conflict_counter += how_many_elements * max_element_list_new[i-1];

          if (i % 1024 == 0)
            Receive(sender);
        }
        for (int i = 1; i < max_element_list_new.size(); ++i) {
          max_element_list[i] += max_element_list_new[i];
        }
        Receive(sender);
        int new_conflict_counter = GetLL(sender);
        conflict_counter += new_conflict_counter;
        // cout << "ODBIERAM od " << sender << endl;
      }
    }
    range *= 2;
  }
  cout << conflict_counter << endl;
  return 0;
}