#include <string>
#include <iostream>
#include <fstream>

using namespace std;
void create_file(string name, int n)
{
    fstream file(name, fstream::out);

    for (int i = 0; i < n; i++)
    {
        file << rand() % 100 << " ";
    }

    file.close();
}

void split(string file_name, int n, int& L, int* a, int* d)// слияние (по лекции)
{
    fstream input(file_name, fstream::in);
    fstream* file = new fstream[n];
    for (int i = 0; i < n - 1; i++)
    {
        file[i].open(to_string(i), fstream::out);

        a[i] = 1;
        d[i] = 1;
    }
    a[n - 1] = 0;
    d[n - 1] = 0;
    L = 1;
    int j = 0;
    int x;
    int y;
    input >> x;
    // 2
    while (true)//пока файл не исчерпан
    {
        // выделяем отрезок
        do
        {
            y = x;
            file[j] << y << endl;
        }
        while (input >> x && y < x);
        file[j] << -1 << endl; // ограничивем -1
        d[j]--;
        if (input.eof())//проверка на конец файла
        {
            break;//выход из цикла
        }
        else
        {
            if (d[j] < d[j + 1])
            {
                j++;
            }
            else if (d[j] == 0) // пересчет уровня и значений в массивах а и d
            {
                L++;
                int tmp = a[0];
                j = 0;

                for (int k = 0; k < n - 1; k++)
                {
                    d[k] = a[k + 1] - a[k] + tmp;
                    a[k] = a[k + 1] + tmp;
                }
            }
            else
            {
                j = 0;
            }
        }
    }
    for (int i = 0; i < n - 1; i++)
    {
        file[i].close();
    }
    input.close();
}

void copy_file(string file1_name, string file2_name) //Копирование файла
{
    fstream from(file1_name, fstream::in);// чтенние
    fstream to(file2_name, fstream::out);// запись

    int a;
    from >> a;
    while (a != -1) // передаем значения из первого файла во второй
    {
        to << a << " ";
        from >> a;
    }

    from.close();
    to.close();
}

bool if_ascent(string name)// возрастающий ли файл
{
    fstream file(name, fstream::in);

    int a, b;
    file >> b;
    while (file >> a)
    {
        if (b > a)
        {
            file.close();
            return false;
        }
        b = a;
    }
    file.close();
    return true;
}

void create_n_file(int n)
{
    for (int i = 0; i < n; i++)
    {
        fstream f(to_string(i), fstream::out);
        f.close();
    }
}

int min(int* arr, int n) //поиск индекса минимума в отрезке
{
    int i;
    for (i = 0; arr[i] == -1 && i < n; i++);
    int _min = i;
    for (i++; i < n; i++)
    {
        if (arr[_min] > arr[i] && arr[i] != -1)
        {
            _min = i;
        }
    }
    return _min;
}

void merge_file(fstream** file, int n, int* a, int* d)// слияние отрезков
{
    int* s = new int[n - 1]; // отрезки
    for (int i = 0; i < n - 1; i++)
    {
        s[i] = -1;
    }
    int end; // конец возрастающего отрезка

    while (a[n - 2] > 0)//пока файл не исчерпается
    {
        end = 0;
        for (int i = 0; i < n - 1; i++)
        {
            if (d[i] > 0)// проверка на фиктивный отрезок
            {
                end++;
                a[i]--;
                d[i]--;
            }
            else
            {
                *file[i] >> s[i];
            }
        }
        while (end < n - 1)
        {
            int _min = min(s, n - 1);
            *file[n - 1] << s[_min] << " ";
            *file[_min] >> s[_min];
            if (s[_min] == -1)
            {
                end++;
                a[_min]--;
            }
        }
        *file[n - 1] << -1 << " ";// ограничиваем -1
    }
}

void merge(string file_name, int n, int& L, int* a, int* d)//Слияние (по лекции)
{
    string* name = new string[n];
    fstream** file = new fstream * [n];

    for (int i = 0; i < n - 1; i++)// открываем файлы f[0]..f[n-2] на чтение
    {
        name[i] = to_string(i);
        file[i] = new fstream(name[i], fstream::in);
    }
    //открываем файл f[n-1] на запись
    name[n - 1] = to_string(n - 1);
    file[n - 1] = new fstream(name[n - 1], fstream::out);

    // 6 пункт
    while (L > 0)// проверка на конец сортировки
    {
        // 7 пункт
        int min = d[0];
        for (int j = 1; j < n - 1; j++)
        {
            if (min > d[j])
                min = d[j];
        }

        if (min > 0)
        {
            int j;
            for ( j = 0; j < n - 1; j++)
            {
                a[j] -= min;
                d[j] -= min;
            }
            d[j] = min;
        }

        merge_file(file, n, a, d);//слияние отрезков

        // 8 пункт
        L--;

        file[n - 2]->close();
        file[n - 1]->close();

        file[n - 2]->open(name[n - 2], fstream::out);
        file[n - 1]->open(name[n - 1], fstream::in);

        //передвигаем указатели на файлы и их имена
        string name_tmp = name[n - 1];
        fstream* file_tmp = file[n - 1];

        int a_tmp = a[n - 1];
        int d_tmp = d[n - 1];

        for (int i = n - 1; i > 0; i--)
        {
            name[i] = name[i - 1];
            file[i] = file[i - 1];

            a[i] = a[i - 1];
            d[i] = d[i - 1];
        }

        name[0] = name_tmp;
        file[0] = file_tmp;

        a[0] = a_tmp;
        d[0] = d_tmp;
    }

    for (int i = 0; i < n - 1; i++)
    {
        file[i]->close();

        delete file[i];
    }

    delete[] file;

    copy_file(name[0], file_name); //переносим значения из f[0] в результирующий файл
}

void main()
{
    int n,L;

    cout << "n = ";
    cin >> n;
    int* a = new int[n];
    int* d = new int[n];

    create_file("StartFile.txt", n); // Создаем исходный файл
    create_n_file(n); // Создаем n файлов
    split("StartFile.txt", n, L, a, d); // Этап 1 разбиение
    merge("ResFile.txt", n, L, a, d);// Этап 2 слияние


    if (if_ascent("ResFile.txt")) // Проверка на возрастающую последовательность
    {
        cout << "Correct" << endl;
    }
    else
    {
        cout << "Incorrect" << endl;
    }
    delete[] d;
    delete[] a;
}