#include <iostream> #include "teatr.h" #include "message.h" using namespace std; typedef unsigned long long ull; const int COORDINATOR_ID = 0; const int NODES_COUNT = 100; const int MAX_INPUT_SIZE = 100 * 1000 * 1000; const int ONE_CHUNK_SIZE = MAX_INPUT_SIZE / NODES_COUNT; const int VALUES_COUNT = 1 << 20; const int HISTOGRAM_TREE_SIZE = 2 * VALUES_COUNT; const int HISTOGRAM_BEGIN = VALUES_COUNT; const int HISTOGRAM_END = 2 * VALUES_COUNT; long long histogram_tree[HISTOGRAM_TREE_SIZE] = { 0 }; inline void histogram_add(int value) { ++histogram_tree[HISTOGRAM_BEGIN + value]; } inline void histogram_tree_build() { int iteration_start = HISTOGRAM_BEGIN / 2; int iteration_end = HISTOGRAM_BEGIN; while (iteration_start != 0) { for (int i = iteration_start; i < iteration_end; ++i) { histogram_tree[i] = histogram_tree[2 * i] + histogram_tree[2 * i + 1]; } iteration_start /= 2; iteration_end /= 2; } } inline long long histogram_tree_add(int value) { int pos = HISTOGRAM_BEGIN + value; long long result = histogram_tree[1] - histogram_tree[pos]; while (pos != 1) { if (pos % 2 == 1) { result -= histogram_tree[pos - 1]; } ++histogram_tree[pos]; pos /= 2; } ++histogram_tree[1]; return result; } inline long long sub_solve(int instance_number) { int pre_start = 0; int proc_start = instance_number * ONE_CHUNK_SIZE; int proc_end = (instance_number + 1) * ONE_CHUNK_SIZE; int pre_end = instance_number == 0 ? 0 : proc_start; long long result = 0; int problem_size = GetN(); if (proc_start >= problem_size) { return result; } if (proc_end > problem_size) { proc_end = problem_size; } for (int i = pre_start; i < pre_end; ++i) { histogram_add(GetElement(i)); } histogram_tree_build(); for (int i = proc_start; i < proc_end; ++i) { result += histogram_tree_add(GetElement(i)); } return result; } inline void gather_results(long long result) { ull accumulated_result = result; for (int i = 1; i < NODES_COUNT; ++i) { Receive(i); accumulated_result += GetLL(i); } cout << accumulated_result << endl; } inline void sent_result(long long result) { PutLL(COORDINATOR_ID, result); Send(COORDINATOR_ID); } inline void solve() { int instance_number = MyNodeId(); long long result = sub_solve(instance_number); if (instance_number == COORDINATOR_ID) { gather_results(result); } else { sent_result(result); } } int main() { ios_base::sync_with_stdio(0); solve(); 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 | #include <iostream> #include "teatr.h" #include "message.h" using namespace std; typedef unsigned long long ull; const int COORDINATOR_ID = 0; const int NODES_COUNT = 100; const int MAX_INPUT_SIZE = 100 * 1000 * 1000; const int ONE_CHUNK_SIZE = MAX_INPUT_SIZE / NODES_COUNT; const int VALUES_COUNT = 1 << 20; const int HISTOGRAM_TREE_SIZE = 2 * VALUES_COUNT; const int HISTOGRAM_BEGIN = VALUES_COUNT; const int HISTOGRAM_END = 2 * VALUES_COUNT; long long histogram_tree[HISTOGRAM_TREE_SIZE] = { 0 }; inline void histogram_add(int value) { ++histogram_tree[HISTOGRAM_BEGIN + value]; } inline void histogram_tree_build() { int iteration_start = HISTOGRAM_BEGIN / 2; int iteration_end = HISTOGRAM_BEGIN; while (iteration_start != 0) { for (int i = iteration_start; i < iteration_end; ++i) { histogram_tree[i] = histogram_tree[2 * i] + histogram_tree[2 * i + 1]; } iteration_start /= 2; iteration_end /= 2; } } inline long long histogram_tree_add(int value) { int pos = HISTOGRAM_BEGIN + value; long long result = histogram_tree[1] - histogram_tree[pos]; while (pos != 1) { if (pos % 2 == 1) { result -= histogram_tree[pos - 1]; } ++histogram_tree[pos]; pos /= 2; } ++histogram_tree[1]; return result; } inline long long sub_solve(int instance_number) { int pre_start = 0; int proc_start = instance_number * ONE_CHUNK_SIZE; int proc_end = (instance_number + 1) * ONE_CHUNK_SIZE; int pre_end = instance_number == 0 ? 0 : proc_start; long long result = 0; int problem_size = GetN(); if (proc_start >= problem_size) { return result; } if (proc_end > problem_size) { proc_end = problem_size; } for (int i = pre_start; i < pre_end; ++i) { histogram_add(GetElement(i)); } histogram_tree_build(); for (int i = proc_start; i < proc_end; ++i) { result += histogram_tree_add(GetElement(i)); } return result; } inline void gather_results(long long result) { ull accumulated_result = result; for (int i = 1; i < NODES_COUNT; ++i) { Receive(i); accumulated_result += GetLL(i); } cout << accumulated_result << endl; } inline void sent_result(long long result) { PutLL(COORDINATOR_ID, result); Send(COORDINATOR_ID); } inline void solve() { int instance_number = MyNodeId(); long long result = sub_solve(instance_number); if (instance_number == COORDINATOR_ID) { gather_results(result); } else { sent_result(result); } } int main() { ios_base::sync_with_stdio(0); solve(); return 0; } |