#include "message.h" #include "teatr.h" #include <iostream> #include <vector> #include <algorithm> constexpr int INSTANCES_NUMBER = 100; constexpr int MAX_HEIGHT = 1000000; long long Merge(int l, int p, std::vector<int>& arr, std::vector<int>& aux){ int s = (l + p) / 2; int i = l, u = l - 1, j = s + 1, it = 0; long long res = 0; while(i <= s && j <= p) { if(arr[i] > arr[j]) { while(arr[u + 1] < arr[j] && u < i) ++u; res += (u - l + 1); aux[it++] = arr[j++]; } else { aux[it++] = arr[i++]; } } while(i <= s) { aux[it++] = arr[i++]; } while(j <= p) { while(arr[u + 1] < arr[j] && u < s) ++u; res += (u - l + 1); aux[it++] = arr[j++]; } for (int i = 0; i < it; i++) { arr[l + i] = aux[i]; } return res; } long long Mergesort(int l, int p, std::vector<int>& arr, std::vector<int>& aux){ int s = (l + p) / 2; long long result = 0; if(l < p){ result += Mergesort(l, s, arr, aux); result += Mergesort(s+1, p, arr, aux); result += Merge(l, p, arr, aux); } return result; } int main() { int node_id = MyNodeId(); int n = GetN(); int block_size = (n + INSTANCES_NUMBER - 1) / INSTANCES_NUMBER; int start = std::min(block_size * node_id, n); int end = std::min(start + block_size, n); std::vector<int> heights(n); std::vector<int> counter(MAX_HEIGHT + 1, 0); for (int i = 0; i < start; i++) { heights[i] = GetElement(n - i - 1); counter[heights[i]]++; } for (int i = start; i < end; i++) { heights[i] = GetElement(n - i - 1); } for (int i = 1; i <= MAX_HEIGHT; i++) { counter[i] += counter[i - 1]; } std::vector<int> aux(n); long long result = (start < end ? Mergesort(start, end - 1, heights, aux) : 0); for (int i = start; i < end; i++) { result += counter[heights[i] - 1]; } if (node_id != 0) { PutLL(0, result); Send(0); } else { for (int i = 1; i < INSTANCES_NUMBER; i++) { result += GetLL(Receive(-1)); } std::cout << result << '\n'; } 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 | #include "message.h" #include "teatr.h" #include <iostream> #include <vector> #include <algorithm> constexpr int INSTANCES_NUMBER = 100; constexpr int MAX_HEIGHT = 1000000; long long Merge(int l, int p, std::vector<int>& arr, std::vector<int>& aux){ int s = (l + p) / 2; int i = l, u = l - 1, j = s + 1, it = 0; long long res = 0; while(i <= s && j <= p) { if(arr[i] > arr[j]) { while(arr[u + 1] < arr[j] && u < i) ++u; res += (u - l + 1); aux[it++] = arr[j++]; } else { aux[it++] = arr[i++]; } } while(i <= s) { aux[it++] = arr[i++]; } while(j <= p) { while(arr[u + 1] < arr[j] && u < s) ++u; res += (u - l + 1); aux[it++] = arr[j++]; } for (int i = 0; i < it; i++) { arr[l + i] = aux[i]; } return res; } long long Mergesort(int l, int p, std::vector<int>& arr, std::vector<int>& aux){ int s = (l + p) / 2; long long result = 0; if(l < p){ result += Mergesort(l, s, arr, aux); result += Mergesort(s+1, p, arr, aux); result += Merge(l, p, arr, aux); } return result; } int main() { int node_id = MyNodeId(); int n = GetN(); int block_size = (n + INSTANCES_NUMBER - 1) / INSTANCES_NUMBER; int start = std::min(block_size * node_id, n); int end = std::min(start + block_size, n); std::vector<int> heights(n); std::vector<int> counter(MAX_HEIGHT + 1, 0); for (int i = 0; i < start; i++) { heights[i] = GetElement(n - i - 1); counter[heights[i]]++; } for (int i = start; i < end; i++) { heights[i] = GetElement(n - i - 1); } for (int i = 1; i <= MAX_HEIGHT; i++) { counter[i] += counter[i - 1]; } std::vector<int> aux(n); long long result = (start < end ? Mergesort(start, end - 1, heights, aux) : 0); for (int i = start; i < end; i++) { result += counter[heights[i] - 1]; } if (node_id != 0) { PutLL(0, result); Send(0); } else { for (int i = 1; i < INSTANCES_NUMBER; i++) { result += GetLL(Receive(-1)); } std::cout << result << '\n'; } return 0; } |