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

int main() {
    int line, column;

    printf("Enter matrix size: ");
    int n;
    scanf("%d", &n);

    // Для хранения массива целых чисел в языке Си используется тип int*.
    // int* означает "указатель на целое число".
    // Указатель -- это тоже целое число, которое буквально означает адрес в памяти компьютера.
    // Т.е., если мы посмотрим реальное значение переменной типа int*, там будет, например, 46485.
    // Это означает "46485-ая ячейка памяти компьютера".
    // Массивы хранятся последовательно, т.е., элементы лежат в памяти друг за другом.
    // Если наш массив состоит из трех элементов, то первый элемент у нас лежит в 46485-ой ячейке памяти.
    // Второй будет лежать в 46486-ой, третий -- в 46487-ой.
    // Значит, для доступа ко всему массиву нам достаточно иметь адрес памяти, в котором лежит первый элемент
    // (т.е., указатель на первый элемент), и дальше просто прибавлять к этому адресу 1, 2 и так далее.
    // Именно поэтому массивы и хранятся в переменной типа int* -- там лежит просто указатель на первый элемент,
    // и оперировать остальными элементами мы можем, просто прибавляя 1, 2, 3 к этому значению.
    // Например, создадим массив целых чисел на 5 элементов.
    // int* array = (int*)malloc(5 * sizeof(int));
    // Функция malloc принимает на вход количество байтов, которые надо выделить и возвращает адрес
    // первого байта выделенной памяти.
    // Функция sizeof принимает на вход тип и возвращает количество байтов, которое он занимает.
    // Следовательно, для того, чтобы выделить достаточно памяти для 5 целых чисел, нам надо
    // узнать, сколько байтов займет одно целое число -- для этого мы вызываем sizeof(int).
    // После этого мы берем это количество байтов столько раз, сколько нам нужно элементов: 5 * sizeof(int),
    // и передаем функции malloc. Она выделяет нам нужное количество памяти и возвращает указатель на первый байт.
    // Из-за того, что malloc не знает, для чего именно она выделяет память (int, float или что-то еще), он возвращает
    // специальный "универсальный" указатель void*. Его мы записать в переменную типа int* не можем, поэтому
    // конвертируем его в int* -- (int*)...
    // Конвертировать значение в другой тип (в терминологии программирования корректно говорить "привести тип")
    // можно так -- перед значением в скобках указывается новый тип. Это мы и делаем, записывая перед malloc в скобках
    // новый тип (int*) -- таким образом void* будет "приведен" к int* и его можно будет спокойно записать
    // в переменную array.
    //
    // С одномерными массивами разобрались, перейдем к матрицам (двумерным массивам).
    // Матрица -- это массив указателей, т.е. массив, у которого каждый из элементов -- указатель на
    // первый элемент другого массива. Еще матрицу называют "массивом массивов", так легче представлять ее в голове.
    // Важно! "Массив массивов" не означает, что каждый элемент массива -- массив. Каждый элемент массива массивов --
    // всего лишь указатель на первый элемент другого массива.
    //
    // Если массив целых чисел хранится как указатель на первое целое число (т.е., int*),
    // то массив массивов целых чисел будет храниться как указатель на указатель на первое целое число.
    // Это будет записываться как int**.
    // Для того, чтобы выделить память под этот самый массив массивов, мы вызываем
    // тот же самый malloc, но теперь нам надо выделить память не на N чисел, а на N указателей на целое число.
    // Соответственно, мы спрашиваем у sizeof размер не целого числа -- sizeof(int),
    // а размер указателя на целое число -- sizeof(int*);

    int** matrix = (int**)malloc(n * sizeof(int*));

    // Мы выделили память для массива массивов, но так как массив массивов -- это всего лишь массив указателей,
    // никто еще не выделил память для самих массивов, на которые эти указатели показывают. На самом деле, самих
    // массивов пока еще не существует, и в данный момент содержимое нашего массива массивов -- это указатели
    // неизвестно куда.
    //
    // Чтобы это исправить, мы N раз выделяем память для массива, который выполняет роль "строки" в нашей матрице
    // и записываем ее в очередной элемент.
    for (line = 0; line < n; ++line) {
        int* line_arr = (int*)malloc(n * sizeof(int));

        // Ранее для записи значения в массив по индексу мы использовали
        // квадратные скобки, примерно таким образом:
        // array[i] = value;
        // Однако запись через квадратные скобки -- лишь синтаксический сахар.
        // По сути, когда нам надо записать значение в элемент массива под индексом i, нам достаточно просто
        // взять указатель на первый элемент массива и прибавить к нему это i.
        // То есть, хотим записать в первый элемент массива (т.е., по индексу 0) -- пишем прямо по адресу array.
        // Хотим записать во второй элемент (по индексу 1) -- пишем по адресу array + 1.
        // Но как нам перейти от указателя к самому значению, на которое он указывает? Тут появляется новая
        // операция -- "разыменование" указателя.
        // Разыменование указателя -- это просто-напросто обращение к той самой памяти, на которую он указывает.
        // Производится оно следующим образом: указывается сам указатель и перед ним ставится звездочка.
        // Например, этот код запишет в переменную value значение, которое находится в массиве arr по индексу 0:
        // int value = *arr;
        // Этот код запишет в переменную value значение, которое находится в массиве arr по индексу 2:
        // int value = *(arr + 2);
        // А этот код запишет в массив arr по индексу 2 цифру 3:
        // *(arr + 2) = 3;
        //
        // Код через разыменование и код через квадратные скобки эквивалентен. Например, три строчки ниже делают
        // абсолютно одно и то же:
        // arr[0] = 3;
        // *(arr + 0) = 3;
        // *arr = 3;
        //
        // Теперь, когда мы это все знаем, мы легко можем понять, что строчка ниже просто напросто берет указатель
        // на свежесозданный массив и записывает его в наш массив массивов по очередному индексу.
        *(matrix + line) = line_arr;
    }

    for (line = 0; line < n; ++line) {
        for (column = 0; column < n; ++column) {
            printf("Enter value at line %d, column %d: ", line, column);

            // scanf требует на вход указатель на элемент. Обычно для этого мы пишем что-то вроде &n
            // (как, например, в этом файле на строке 9). & (амперсанд) перед именем переменной возвращает указатель
            // на нее. В нашем случае вместо этого мы просто не разыменовываем указатель на элемент и передаем в scanf
            // сразу его.
            scanf("%d", (*(matrix + line) + column));
            printf("\n");
        }
    }

    // Выводим исходную матрицу.
    printf("Исходная матрица:\n");
    for (line = 0; line < n; ++line) {
        for (column = 0; column < n; ++column) {
            printf("%3d ", *(*(matrix + line) + column));
        }

        printf("\n");
    }

    // Количество уникальных элементов в матрице заранее известно и вычисляется по этой формуле.
    int unique_values_count = (n * n) / 4;

    // Нам нужно следить, сколько уникальных элементов мы уже нашли, чтобы знать, по какому индексу их записывать
    // в массив, где мы храним все уникальные значения.
    int found_values_count = 0;

    // Массив, в котором хранятся все уникальные значения. Из него мы будем собирать новую матрицу.
    int* unique_values = (int*)malloc(unique_values_count * sizeof(int));
    int unique_values_index;

    // Перебираем все элементы матрицы
    for (line = 0; line < n; ++line) {
        // Если мы уже нашли все уникальные значения, дальше перебирать матрицу смысла нет.
        if (found_values_count == unique_values_count)
            break;

        int* line_arr = *(matrix + line);
        for (column = 0; column < n; ++column) {

            // Проверка аналогична проверке выше, необходимо указать и здесь, чтобы не перебирать строчку до конца.
            if (found_values_count == unique_values_count)
                break;

            int value = *(line_arr + column);

            for (unique_values_index = 0; unique_values_index < found_values_count; ++unique_values_index) {
                int found_value = *(unique_values + unique_values_index);

                // Если элемент нашелся в массиве уникальных элементов, он "неуникальный" и мы переходим к другому.
                if (found_value == value) {
                    break;
                }
            }

            // Если мы пришли сюда, значит, break на 140 строке не выполнился и элемент уникальный.
            // Записываем его в массив уникальных значений.
            *(unique_values + found_values_count) = value;
            ++found_values_count;
        }
    }

    // Создаем новую матрицу размера n/2 на n/2.
    int new_matrix_line;
    int** new_matrix = (int**)malloc((n / 2) * sizeof(int*));
    for (new_matrix_line = 0; new_matrix_line < n / 2; ++new_matrix_line) {
        *(new_matrix + new_matrix_line) = (int*)malloc((n / 2) * sizeof(int));
    }

    // По условию задания мы заполняем новую матрицу не как обычно, по строкам, а по столбцам
    // (т.е. берем каждый столбец и перебираем номер строки).
    new_matrix_line = 0;
    int new_matrix_column = 0;
    for (unique_values_index = 0; unique_values_index < unique_values_count; ++unique_values_index) {
        // Перебираем по очереди элементы массива уникальных значений и записываем их в матрицу,
        // каждый раз увеличивая номер строки
        *(*(new_matrix + new_matrix_line) + new_matrix_column) = *(unique_values + unique_values_index);
        ++new_matrix_line;

        // Если после этого new_matrix_line стала равна размеру новой матрицы (т.е., все строчки текущего столбца
        // заполнены), мы обнуляем ее и увеличиваем номер столбца на 1, чтобы приступить к следующему столбцу.
        if (new_matrix_line == n / 2) {
            ++new_matrix_column;
            new_matrix_line = 0;
        }
    }

    // Выводим получившуюся матрицу.
    printf("Итоговая матрица:\n");
    for (new_matrix_line = 0; new_matrix_line < n / 2; ++new_matrix_line) {
        for (new_matrix_column = 0; new_matrix_column < n / 2; ++new_matrix_column) {
            printf("%3d ", *(*(new_matrix + new_matrix_line) + new_matrix_column));
        }

        printf("\n");
    }
}