page 79 problem 20

#include<bits/stdc++.h>

using namespace std;


#define Line cout << endl << "-------------------------------------------\n\n"
#define forn(i, n) for(int i = 0; i < int(n);i++)
const int INF = 1e9 + 13;
const int N = 1e5 + 13;

bool comparator(int a, int b, string s){
    return (s == "Greater") ? a < b : a > b;
}
template<typename T> void My_sort(T* arr, int n, string rule){
   for(int i = 0; i < n; i++)
        for(int j = i; j > 0 && comparator(arr[j - 1], arr[j], rule); j--)
            swap(arr[j - 1], arr[j]);
}
template<typename T> T* Get_Line(T** a, int k, int n){
    int SIZE, i, j, ptr = 0;
    if (k < n){
        SIZE = k + 1;
        i = n - k - 1;
        j = 0;
    }
    else{
        SIZE = 2 * n - 1 - k;
        i = 0;
        j = k - n + 1;
    }
    T* res = new T[SIZE];
    while(i < n && j < n)
        res[ptr++] = a[i++][j++];
    return res;
}
template<typename T> void Replace(T** a, const T* arr, int k, int n){
    int i, j, ptr = 0;
    if (k < n){
        i = n - k - 1;
        j = 0;
    }
    else{
        i = 0;
        j = k - n + 1;
    }
    while(i < n && j < n)
        a[i++][j++] = arr[ptr++];
}
template<typename T> void print_a(T** a, int n){
    Line;
    forn(i, n){
        forn(j, n)
            cout << a[i][j] << ' ';
        cout << '\n';
    }
}
template<typename T> T** init(int n){
    T** a = new int*[n];
    forn(i, n)
        a[i] = new int[n];
    forn(i, n)
        forn(j, n)
            cin >> a[i][j];
    return a;
}
int main(){
    int n;
    cin >> n;
    int** a = init(n);
    forn(k, n * 2 - 1){
        string RULE;
        int SIZE;
        if (k < n)
            RULE = "Little";
        else
            RULE = "Greater";
        if (k < n)
            SIZE = k + 1;
        else
            SIZE = 2*n - k - 1;

        int* temp = Get_Line(a, k, n);
        My_sort(temp, SIZE, RULE);
        Replace(a, temp, k, n);
        delete [] temp;
    }
    print_a(a, n);
}