StoneHaos

my23

May 31st, 2020
115
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. template <typename T>
  6. void myswap(T& a, T& b) {
  7.     T tmp = a;
  8.     a = b;
  9.     b = tmp;
  10. }
  11.  
  12. template <typename T>
  13. void qs(T* arr, int n, int (*comp)(T, T)) {
  14.     if (n <= 1)
  15.         return;
  16.     int left = 0;
  17.     int right = n - 1;
  18.     int pivot = (n - 1) >> 1;
  19.     while (left < right) {
  20.         while (left < pivot && comp(arr[left], arr[pivot]) != 1) ++ left;
  21.         while (right > pivot && comp(arr[right], arr[pivot]) != -1) -- right;
  22.         if (comp(arr[left], arr[right]) == 1) {
  23.             if (left == pivot)
  24.                 pivot = right;
  25.             else if (right == pivot)
  26.                 pivot = left;
  27.             myswap(arr[left], arr[right]);
  28.         }
  29.     }
  30.     if (n == 2)
  31.         return;
  32.     qs(arr, pivot, comp);
  33.     qs(arr + pivot, n - pivot, comp);
  34. }
  35.  
  36. template <typename T>
  37. bool find(T* arr, int n, T elem) {
  38.     for (int i = 0; i < n; ++ i)
  39.         if (arr[i] == elem)
  40.             return true;
  41.     return false;
  42. }
  43.  
  44. template <typename T>
  45. T* append(T* arr, int& n, T elem) {
  46.     T* old = arr;
  47.     arr = new T[n + 1];
  48.     for (int i = 0; i < n; ++ i)
  49.         arr[i] = old[i];
  50.     arr[n ++] = elem;
  51.     delete [] old;
  52.     return arr;
  53. }
  54.  
  55. int compare(int* a, int* b) {
  56.     int x = a[a[0] + 1], y = b[b[0] + 1];
  57.     if (x < y)
  58.         return 1;
  59.     else if (x > y)
  60.         return -1;
  61.     else
  62.         return 0;
  63. }
  64.  
  65. int main(void) {
  66.     time_t t = time(NULL);
  67.     printf("t = %lu\n", t);
  68.     srand(t);
  69.  
  70.     int n, m;
  71.     scanf("%d%d", &n, &m);
  72.     int **arr = new int*[n];
  73.     printf("old:\n");
  74.     for (int i = 0; i < n; ++ i) {
  75.         arr[i] = new int[m + 2];
  76.         arr[i][0] = m;
  77.         int cnt = 0, *rep = new int[cnt];
  78.         for (int j = 1; j <= m; ++ j) {
  79.             arr[i][j] = rand() % 10 - 3;
  80.             printf("%2d ", arr[i][j]);
  81.             if (!find(rep, cnt, arr[i][j]))
  82.                 rep = append(rep, cnt, arr[i][j]);
  83.         }
  84.         arr[i][m + 1] = cnt;
  85.         delete [] rep;
  86.         printf("\n");
  87.     }
  88.  
  89.     qs(arr, n, compare);
  90.  
  91.     printf("\n\nnew:\n");
  92.     for (int i = 0; i < n; ++ i) {
  93.         for (int j = 1; j <= m; ++ j)
  94.             printf("%2d ", arr[i][j]);
  95.         printf("\n");
  96.     }
  97.  
  98.     printf("\n\n");
  99.     bool flag = true;
  100.     for (int j = 1; j <= m; ++ j) {
  101.         flag = true;
  102.         for (int i = 0; i < n; ++ i)
  103.             if (arr[i][j] < 0)
  104.                 flag = false;
  105.         if (flag) {
  106.             printf("N = %d\n", j);
  107.             break;
  108.         }
  109.     }
  110.     if (!flag)
  111.         printf("Not found\n");
  112.  
  113.     for (int i = 0; i < n; ++ i)
  114.         delete [] arr[i];
  115.     delete [] arr;
  116.     return 0;
  117. }
RAW Paste Data