#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; }
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; } |