#include <iostream> #include <math.h> #include "message.h" #include "teatr.h" #include "bits/stdc++.h" #define LL long long #define MIN_N 1000 #define MAX_SIZE 1000010 #define MAX_LENGTH 100000000 using namespace std; LL merge(int *values, int start, int mid, int end) { LL count = 0; int first[mid-start+2], second[end-mid+1], i, j, L; j = 0; for (i = start; i < mid+1; i++) first[j++] = values[i]; first[j] = MAX_SIZE; L = j + 1; j = 0; for (i = mid + 1; i < end+1; i++) second[j++] = values[i]; second[j] = MAX_SIZE; i = 0, j = 0; for (int k = start; k < end+1; k++) { if (first[i] <= second[j]) values[k] = first[i++]; else { values[k] = second[j++]; count += L - i - 1; } } return count; } LL mergesort(int *values, int start, int end) { LL count = 0; int mid; if (start < end) { mid = (start + end) / 2; count += mergesort(values, start, mid); count += mergesort(values, mid + 1, end); count += merge(values, start, mid, end); } return count; } int main() { int nodes, node_id, N, n, v, k, i; int values[MAX_SIZE]; int left[MAX_SIZE], max_v; int k_start, k_stop, eff_node_id, next_node_id = 1, conn_node_id; LL count = 0, right_count; nodes = NumberOfNodes(); node_id = MyNodeId(); N = GetN(); n = max(N / nodes + 1, MIN_N); k_start = n * node_id; k_stop = min(n * (node_id + 1), N); if (k_start < k_stop) { i = -1; for (k = k_start; k < k_stop; k++){ values[++i] = GetElement(k); } count = mergesort(values, 0, i); } else return 0; eff_node_id = node_id; while (true) { if (eff_node_id % 2 == 0) { conn_node_id = node_id + next_node_id; if (n * conn_node_id < N) { Receive(conn_node_id); right_count = GetLL(conn_node_id); } else if (node_id > 0) { eff_node_id /= 2; next_node_id *= 2; continue; } else break; count += right_count; for (k = 0; k < MAX_SIZE; k++) left[k] = 0; k_start = n * node_id; k_stop = n * conn_node_id; max_v = 0; for (k = k_start; k < k_stop; k++) { v = GetElement(k); left[v]++; if (v > max_v) max_v = v; } for (k = max_v; k > 0; k--){ left[k-1] += left[k]; } k_start = n * conn_node_id; k_stop = min(n * (conn_node_id + next_node_id), N); for (k = k_start; k < k_stop; k++) { v = GetElement(k); if (v < max_v) { count += left[v+1]; } } } else { // send value conn_node_id = node_id - next_node_id; PutLL(conn_node_id, count); Send(conn_node_id); return 0; } eff_node_id /= 2; next_node_id *= 2; } cout << count << 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 121 122 123 124 125 126 127 128 129 | #include <iostream> #include <math.h> #include "message.h" #include "teatr.h" #include "bits/stdc++.h" #define LL long long #define MIN_N 1000 #define MAX_SIZE 1000010 #define MAX_LENGTH 100000000 using namespace std; LL merge(int *values, int start, int mid, int end) { LL count = 0; int first[mid-start+2], second[end-mid+1], i, j, L; j = 0; for (i = start; i < mid+1; i++) first[j++] = values[i]; first[j] = MAX_SIZE; L = j + 1; j = 0; for (i = mid + 1; i < end+1; i++) second[j++] = values[i]; second[j] = MAX_SIZE; i = 0, j = 0; for (int k = start; k < end+1; k++) { if (first[i] <= second[j]) values[k] = first[i++]; else { values[k] = second[j++]; count += L - i - 1; } } return count; } LL mergesort(int *values, int start, int end) { LL count = 0; int mid; if (start < end) { mid = (start + end) / 2; count += mergesort(values, start, mid); count += mergesort(values, mid + 1, end); count += merge(values, start, mid, end); } return count; } int main() { int nodes, node_id, N, n, v, k, i; int values[MAX_SIZE]; int left[MAX_SIZE], max_v; int k_start, k_stop, eff_node_id, next_node_id = 1, conn_node_id; LL count = 0, right_count; nodes = NumberOfNodes(); node_id = MyNodeId(); N = GetN(); n = max(N / nodes + 1, MIN_N); k_start = n * node_id; k_stop = min(n * (node_id + 1), N); if (k_start < k_stop) { i = -1; for (k = k_start; k < k_stop; k++){ values[++i] = GetElement(k); } count = mergesort(values, 0, i); } else return 0; eff_node_id = node_id; while (true) { if (eff_node_id % 2 == 0) { conn_node_id = node_id + next_node_id; if (n * conn_node_id < N) { Receive(conn_node_id); right_count = GetLL(conn_node_id); } else if (node_id > 0) { eff_node_id /= 2; next_node_id *= 2; continue; } else break; count += right_count; for (k = 0; k < MAX_SIZE; k++) left[k] = 0; k_start = n * node_id; k_stop = n * conn_node_id; max_v = 0; for (k = k_start; k < k_stop; k++) { v = GetElement(k); left[v]++; if (v > max_v) max_v = v; } for (k = max_v; k > 0; k--){ left[k-1] += left[k]; } k_start = n * conn_node_id; k_stop = min(n * (conn_node_id + next_node_id), N); for (k = k_start; k < k_stop; k++) { v = GetElement(k); if (v < max_v) { count += left[v+1]; } } } else { // send value conn_node_id = node_id - next_node_id; PutLL(conn_node_id, count); Send(conn_node_id); return 0; } eff_node_id /= 2; next_node_id *= 2; } cout << count << endl; return 0; } |