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.
#include <bits/stdc++.h> // Algorytm Count Inversions zosta� zaczerpniety z gfg zamieszczam link pod spodem #include "teatr.h" // https://www.geeksforgeeks.org/counting-inversions/ #include "message.h" using namespace std; int arr[10000009]; int _mergeSort(int arr[], int temp[], int left, int right); int merge(int arr[], int temp[], int left, int mid, int right); int mergeSort(int arr[], int array_size) { int* temp = (int*)malloc(sizeof(int) * array_size); return _mergeSort(arr, temp, 0, array_size - 1); } int _mergeSort(int arr[], int temp[], int left, int right) { int mid, inv_count = 0; if (right > left) { mid = (right + left) / 2; inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } int merge(int arr[], int temp[], int left, int mid, int right) { int i, j, k; int 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 = inv_count + (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; } int n; int main() { int id=MyNodeId(); n=GetN(); if(id>0) return 0; n=GetN(); for(int i=0; i<n; i++) { arr[i]=GetElement(i); } printf("%d \n", mergeSort(arr, 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 | #include <bits/stdc++.h> // Algorytm Count Inversions zosta� zaczerpniety z gfg zamieszczam link pod spodem #include "teatr.h" // https://www.geeksforgeeks.org/counting-inversions/ #include "message.h" using namespace std; int arr[10000009]; int _mergeSort(int arr[], int temp[], int left, int right); int merge(int arr[], int temp[], int left, int mid, int right); int mergeSort(int arr[], int array_size) { int* temp = (int*)malloc(sizeof(int) * array_size); return _mergeSort(arr, temp, 0, array_size - 1); } int _mergeSort(int arr[], int temp[], int left, int right) { int mid, inv_count = 0; if (right > left) { mid = (right + left) / 2; inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } int merge(int arr[], int temp[], int left, int mid, int right) { int i, j, k; int 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 = inv_count + (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; } int n; int main() { int id=MyNodeId(); n=GetN(); if(id>0) return 0; n=GetN(); for(int i=0; i<n; i++) { arr[i]=GetElement(i); } printf("%d \n", mergeSort(arr, n)); return 0; } |