#include <iostream> #include <cstdio> #include <string> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <algorithm> #include <cstring> #include <ctime> #include <cassert> #include "teatr.h" #include "message.h" using namespace std; using ll = long long; const ll INF = 1e9+10; const int MASTER = 0; const int MAX_VAL = 1e6+10; // Test Tomasz Nowak /* int GetN() { return int(1e8); } int GetElement(int i) { return (i * 1ll * i) % int(1e6) + 1; } */ // Test Mateusz Lewko 1 /* int GetN() { return 100 * 1000 * 1000; } int GetElement(int i) { return 1 + (((ll)i * 27) + i & (i %113) + ((i % 37) ^ (i % 20)) * 3571) % 1000000; } */ // Test Mateusz Lewko 2 /* int GetN() { return 100 * 1000 * 1000; } int GetElement(int i) { if (i < 100 * 1000 * 1000 - 3) return 1 + i / 100; else return 100 * 1000 * 1000 - i; } */ int bt[MAX_VAL+10]; int bt_query(int x) { int res = 0; ++x; while (x > 0) { res += bt[x]; x -= (x & (-x)); } return res; } void bt_increment(int x) { ++x; while (x <= MAX_VAL+1) { ++bt[x]; x += (x & (-x)); } } int cnt[MAX_VAL+10]; int larger[MAX_VAL+10]; int main() { const int id = MyNodeId(); const int n = GetN(); const int k = min(n, NumberOfNodes()); //don't need such instances if (id >= k) return 0; const int block_len = ceil(n / (double)k); const int range_begin = id*block_len; const int range_end = min(n-1, (id+1)*block_len-1); const int range_len = range_end-range_begin+1; // computing local result ll inv_count = 0; // bit tree variant from the end, so with one query instead of two for (int i = range_end; i >= range_begin; --i) { int x = GetElement(i); inv_count += bt_query(x-1); bt_increment(x); } PutLL(MASTER, inv_count); Send(MASTER); if (id == MASTER) { // joining results ll res = 0; for (int sender_id = 0; sender_id < k; ++sender_id) { Receive(sender_id); ll sender_result = GetLL(sender_id); res += sender_result; } for (int block_start = 0; block_start < n; block_start += range_len) { for (int i = block_start; i < min(n, block_start+range_len); ++i) { int x = GetElement(i); res += larger[x]; ++cnt[x]; } for (int x = MAX_VAL; x >= 0; --x) { larger[x] = larger[x+1] + cnt[x+1]; } } printf("%lld\n", res); } 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 <iostream> #include <cstdio> #include <string> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <algorithm> #include <cstring> #include <ctime> #include <cassert> #include "teatr.h" #include "message.h" using namespace std; using ll = long long; const ll INF = 1e9+10; const int MASTER = 0; const int MAX_VAL = 1e6+10; // Test Tomasz Nowak /* int GetN() { return int(1e8); } int GetElement(int i) { return (i * 1ll * i) % int(1e6) + 1; } */ // Test Mateusz Lewko 1 /* int GetN() { return 100 * 1000 * 1000; } int GetElement(int i) { return 1 + (((ll)i * 27) + i & (i %113) + ((i % 37) ^ (i % 20)) * 3571) % 1000000; } */ // Test Mateusz Lewko 2 /* int GetN() { return 100 * 1000 * 1000; } int GetElement(int i) { if (i < 100 * 1000 * 1000 - 3) return 1 + i / 100; else return 100 * 1000 * 1000 - i; } */ int bt[MAX_VAL+10]; int bt_query(int x) { int res = 0; ++x; while (x > 0) { res += bt[x]; x -= (x & (-x)); } return res; } void bt_increment(int x) { ++x; while (x <= MAX_VAL+1) { ++bt[x]; x += (x & (-x)); } } int cnt[MAX_VAL+10]; int larger[MAX_VAL+10]; int main() { const int id = MyNodeId(); const int n = GetN(); const int k = min(n, NumberOfNodes()); //don't need such instances if (id >= k) return 0; const int block_len = ceil(n / (double)k); const int range_begin = id*block_len; const int range_end = min(n-1, (id+1)*block_len-1); const int range_len = range_end-range_begin+1; // computing local result ll inv_count = 0; // bit tree variant from the end, so with one query instead of two for (int i = range_end; i >= range_begin; --i) { int x = GetElement(i); inv_count += bt_query(x-1); bt_increment(x); } PutLL(MASTER, inv_count); Send(MASTER); if (id == MASTER) { // joining results ll res = 0; for (int sender_id = 0; sender_id < k; ++sender_id) { Receive(sender_id); ll sender_result = GetLL(sender_id); res += sender_result; } for (int block_start = 0; block_start < n; block_start += range_len) { for (int i = block_start; i < min(n, block_start+range_len); ++i) { int x = GetElement(i); res += larger[x]; ++cnt[x]; } for (int x = MAX_VAL; x >= 0; --x) { larger[x] = larger[x+1] + cnt[x+1]; } } printf("%lld\n", res); } return 0; } |