Niestety, nie byliśmy w stanie w pełni poprawnie wyświetlić tego pliku, ponieważ nie jest zakodowany w UTF-8.
Możesz pobrać ten plik i spróbować otworzyć go samodzielnie.
// https://www.geeksforgeeks.org/counting-inversions/ // funkcja _mergeSort zosta�a pobrana z tej strony #include <iostream> #include <cstdio> #include "message.h" #include "teatr.h" using namespace std; int arr[2500005]; int temp[2500005]; int ile[1000005]; int niewieksze[1000005]; int n, m, nr, pocz, kon, dl; long long wynik, inwersje; /*int GetN() {} int GetElement(int i) {} int MyNodeId() {} void PutLL(int target, long long value) {} void Send(int target) {} int Receive(int source) {} long long GetLL(int source) {}*/ long long merge (int left, int mid, int right) { int i, j, k; long long inv_count = 0; i = left; j = mid; k = left; while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else { temp[k++] = arr[j++]; inv_count += (long long)(mid - i); } } while (i <= mid - 1) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } long long _mergeSort (int left, int right) { int mid; long long inv_count = 0; if (right > left) { mid = (right + left) / 2; inv_count = _mergeSort(left, mid); inv_count += _mergeSort(mid + 1, right); inv_count += merge(left, mid + 1, right); } return inv_count; } int main () { wynik = 0; n = GetN(); nr = MyNodeId(); pocz = (n / 100) * nr; if (nr != 99) kon = (n / 100) * (nr + 1); else kon = n; dl = kon - pocz; for (int i = 0; i < dl; ++i) arr[i] = GetElement(i + pocz); for (int i = kon; i < n; ++i) { m = GetElement(i); ile[m]++; } for (int i = 1; i <= 1000000; ++i) niewieksze[i] = niewieksze[i - 1] + ile[i]; for (int i = 0; i < dl; ++i) wynik += (long long)(niewieksze[arr[i] - 1]); inwersje = _mergeSort(0, dl - 1); wynik += inwersje; if (nr != 0) { PutLL(0, wynik); Send(0); } if (nr == 0) { for (int i = 1; i < 100; ++i) { Receive(i); inwersje = GetLL(i); wynik += inwersje; } printf("%lld\n", wynik); } 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 | // https://www.geeksforgeeks.org/counting-inversions/ // funkcja _mergeSort zosta�a pobrana z tej strony #include <iostream> #include <cstdio> #include "message.h" #include "teatr.h" using namespace std; int arr[2500005]; int temp[2500005]; int ile[1000005]; int niewieksze[1000005]; int n, m, nr, pocz, kon, dl; long long wynik, inwersje; /*int GetN() {} int GetElement(int i) {} int MyNodeId() {} void PutLL(int target, long long value) {} void Send(int target) {} int Receive(int source) {} long long GetLL(int source) {}*/ long long merge (int left, int mid, int right) { int i, j, k; long long inv_count = 0; i = left; j = mid; k = left; while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else { temp[k++] = arr[j++]; inv_count += (long long)(mid - i); } } while (i <= mid - 1) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } long long _mergeSort (int left, int right) { int mid; long long inv_count = 0; if (right > left) { mid = (right + left) / 2; inv_count = _mergeSort(left, mid); inv_count += _mergeSort(mid + 1, right); inv_count += merge(left, mid + 1, right); } return inv_count; } int main () { wynik = 0; n = GetN(); nr = MyNodeId(); pocz = (n / 100) * nr; if (nr != 99) kon = (n / 100) * (nr + 1); else kon = n; dl = kon - pocz; for (int i = 0; i < dl; ++i) arr[i] = GetElement(i + pocz); for (int i = kon; i < n; ++i) { m = GetElement(i); ile[m]++; } for (int i = 1; i <= 1000000; ++i) niewieksze[i] = niewieksze[i - 1] + ile[i]; for (int i = 0; i < dl; ++i) wynik += (long long)(niewieksze[arr[i] - 1]); inwersje = _mergeSort(0, dl - 1); wynik += inwersje; if (nr != 0) { PutLL(0, wynik); Send(0); } if (nr == 0) { for (int i = 1; i < 100; ++i) { Receive(i); inwersje = GetLL(i); wynik += inwersje; } printf("%lld\n", wynik); } return 0; } |