my23

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

template <typename T>
void myswap(T& a, T& b) {
    T tmp = a;
    a = b;
    b = tmp;
}

template <typename T>
void qs(T* arr, int n, int (*comp)(T, T)) {
    if (n <= 1)
        return;
    int left = 0;
    int right = n - 1;
    int pivot = (n - 1) >> 1;
    while (left < right) {
        while (left < pivot && comp(arr[left], arr[pivot]) != 1) ++ left;
        while (right > pivot && comp(arr[right], arr[pivot]) != -1) -- right;
        if (comp(arr[left], arr[right]) == 1) {
            if (left == pivot)
                pivot = right;
            else if (right == pivot)
                pivot = left;
            myswap(arr[left], arr[right]);
        }
    }
    if (n == 2)
        return;
    qs(arr, pivot, comp);
    qs(arr + pivot, n - pivot, comp);
}

template <typename T>
bool find(T* arr, int n, T elem) {
    for (int i = 0; i < n; ++ i)
        if (arr[i] == elem)
            return true;
    return false;
}

template <typename T>
T* append(T* arr, int& n, T elem) {
    T* old = arr;
    arr = new T[n + 1];
    for (int i = 0; i < n; ++ i)
        arr[i] = old[i];
    arr[n ++] = elem;
    delete [] old;
    return arr;
}

int compare(int* a, int* b) {
    int x = a[a[0] + 1], y = b[b[0] + 1];
    if (x < y)
        return 1;
    else if (x > y)
        return -1;
    else
        return 0;
}

int main(void) {
    time_t t = time(NULL);
    printf("t = %lu\n", t);
    srand(t);

    int n, m;
    scanf("%d%d", &n, &m);
    int **arr = new int*[n];
    printf("old:\n");
    for (int i = 0; i < n; ++ i) {
        arr[i] = new int[m + 2];
        arr[i][0] = m;
        int cnt = 0, *rep = new int[cnt];
        for (int j = 1; j <= m; ++ j) {
            arr[i][j] = rand() % 10 - 3;
            printf("%2d ", arr[i][j]);
            if (!find(rep, cnt, arr[i][j]))
                rep = append(rep, cnt, arr[i][j]);
        }
        arr[i][m + 1] = cnt;
        delete [] rep;
        printf("\n");
    }

    qs(arr, n, compare);

    printf("\n\nnew:\n");
    for (int i = 0; i < n; ++ i) {
        for (int j = 1; j <= m; ++ j)
            printf("%2d ", arr[i][j]);
        printf("\n");
    }

    printf("\n\n");
    bool flag = true;
    for (int j = 1; j <= m; ++ j) {
        flag = true;
        for (int i = 0; i < n; ++ i)
            if (arr[i][j] < 0)
                flag = false;
        if (flag) {
            printf("N = %d\n", j);
            break;
        }
    }
    if (!flag)
        printf("Not found\n");

    for (int i = 0; i < n; ++ i)
        delete [] arr[i];
    delete [] arr;
    return 0;
}