#include <fstream>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <random>
#include <iomanip>
using namespace std;
vector<int> r,d,p,w;
int n,t;

int F(vector<int> &p2)
{
    int ans = 0;
    for (auto it : p2) {
        ans += w[it];
    }
    return ans;
}

int T(vector<int> &p1, int t, int blocked) {
    int tm = t;
    for (auto it:p1) {
        if (it != blocked) {
            if (r[it]>tm)
                tm = r[it];
            tm += p[it];
        }
    }
    return tm;
}

void ConsoleInput()
{
    cerr << "Введите n: ";
    cin >> n;
    cerr << "Введите t: ";
    cin >> t;
    r.resize(n);
    cerr << "Введите r_i: ";
    for (int i = 0; i < n; i++)
        cin >> r[i];
    d.resize(n);
    cerr << "Введите d_i: ";
    for (int i = 0; i < n; i++)
        cin >> d[i];
    p.resize(n);
    cerr << "Введите p_i: ";
    for (int i = 0; i < n; i++)
        cin >> p[i];
    w.resize(n);
    cerr << "Введите w_i: ";
    for (int i = 0; i < n; i++)
        cin >> w[i];
}

bool FileInput(const string &path) // считывание с файла
{
    ifstream file_in(path);
    if (!(file_in >> n >> t))
        return false;
    r.resize(n);
    for (int i = 0; i < n; i++)
        if (!(file_in >> r[i]))
            return false;
    d.resize(n);
    for (int i = 0; i < n; i++)
        if (!(file_in >> d[i]))
            return false;
    p.resize(n);
    for (int i = 0; i < n; i++)
        if (!(file_in >> p[i]))
            return false;
    w.resize(n);
    for (int i = 0; i < n; i++)
        if (!(file_in >> w[i]))
            return false;
    return true;
}



pair<vector<int>, vector<int>> FirstModification()
{
    int tk = t;
    vector<int> p1, p2;
    queue<int> nk;
    for (int i = 0; i < n; i++)
        nk.push(i);
    while (!nk.empty()) {
        int i = nk.front();
        if (r[i]>tk)
            tk = r[i];
        if (tk + p[i] <= d[i])
        {
            p2.push_back(i);
            tk += p[i];
            nk.pop();
        } else {
            int ind1 = 0;
            int ind2 = 0;
            p2.push_back(i);

            vector<int> cand(p2.size());
            for (int j = 0; j < p2.size(); j++) {
                cand[j] = T(p2, t, p2[j]);
                if (cand[ind1] > cand[j]) {
                    ind1 = j;
                }
                if (w[p2[ind2]]> w[p2[j]]) {
                    ind2 = j;
                }
            }
            int m = -1;
            for (int j = 0; j < p2.size(); j++) {
                if (cand[j]== cand[ind1] && w[p2[j]] == w[p2[ind2]]) {
                    m = j;
                }
            }
            if (m == -1)
            {
                m = ind1;
                for (int j = 0; j < p2.size(); j++)
                    if (cand[j]== cand[m] && w[p2[j]] < w[p2[m]]) {
                        m = j;
                    }
            }
            if (p2[m] == i) {
                p2.pop_back();
                p1.push_back(i);
                nk.pop();
            } else {
                p2.pop_back();
                p1.push_back(p2[m]);
                p2.erase(p2.begin() + m);
                tk = T(p2, t, -1);
            }
        }
    }
    return {p2, p1};
}

pair<vector<int>, vector<int>> SecondModification()
{
    int tk = t;
    vector<int> p1, p2;
    queue<int> nk;
    for (int i = 0; i < n; i++)
        nk.push(i);
    while (!nk.empty()) {
        int i = nk.front();
        tk = max(tk, r[i]);
        if (tk + p[i] <= d[i])
        {
            p2.push_back(i);
            tk += p[i];
            nk.pop();
        } else {
            int ind1 = 0;
            int ind2 = 0;
            p2.push_back(i);

            vector<int> cand(p2.size());
            for (int j = 0; j < p2.size(); j++) {
                cand[j] = T(p2, t, p2[j]);
                if (cand[ind1] > cand[j]) {
                    ind1 = j;
                }
                if (w[p2[ind2]]> w[p2[j]]) {
                    ind2 = j;
                }
            }
            int m = -1;
            for (int j = 0; j < p2.size(); j++) {
                if (cand[j]== cand[ind1] && w[p2[j]] == w[p2[ind2]]) {
                    m = j;
                }
            }
            if (m == -1)
            {
                m = ind2;
                for (int j = 0; j < p2.size(); j++) {
                    if (w[p2[j]]== w[p2[m]] &&
                        cand[j]< cand[m]) {
                        m = j;
                    }
                }
            }
            if (p2[m] == i) {
                p2.pop_back();
                p1.push_back(i);
                nk.pop();
            } else {
                p2.pop_back();
                p1.push_back(p2[m]);
                p2.erase(p2.begin() + m);
                tk = T(p2, t, -1);
            }
        }
    }
    return {p2, p1};
}
void display(ostream &cout) {
    cout << "N = " << n << " t = " << t << endl;
    cout << "r = ";
    for (int i = 0; i < n; i++)
        cout << r[i] << " ";
    cout << endl;
    cout << "d = ";
    for (int i = 0; i < n; i++)
        cout << d[i] << " ";
    cout << endl;
    cout << "p = ";
    for (int i = 0; i < n; i++)
        cout << p[i] << " ";
    cout << endl;
    cout << "w = ";
    for (int i = 0; i < n; i++)
        cout << w[i] << " ";
    cout << endl;
}

void solve(int disp, ostream &cout) {
    auto firstResult = FirstModification();
    cout << "Результат первой модификации";
    cout << endl << "Запаздывающие требования: ";
    for (auto elem : firstResult.second)
        cout << elem + 1 << " ";

    cout << endl << "Незапаздывающие требования: ";
    for (auto elem : firstResult.first)
        cout << elem + 1 << " ";

    cout << endl <<"Сумма весов запаздывающих требований: " << F(firstResult.second) << endl << endl;
    if (disp) {
        cerr << "Результат первой модификации" << endl;
        cerr << "Запаздывающие требования: ";
        for (auto it : firstResult.second)
            cerr << it + 1 << " ";

        cerr << endl << "Незапаздывающие требования: ";
        for (auto it : firstResult.first)
            cerr << it + 1 << " ";
        cerr << endl<<"Сумма весов запаздывающих требований: " << F(firstResult.second) <<
             endl << endl;
    }
    auto secondResult = SecondModification();
    cout << "Результат второй модификации";

    cout << endl << "Запаздывающие требования: ";
    for (auto it : secondResult.second)
        cout << it + 1 << " ";

    cout << endl <<"Незапаздывающие требования: ";
    for (auto it : secondResult.first)
        cout << it + 1 << " ";

    cout << endl<<"Сумма весов запаздывающих требований: " << F(secondResult.second) << endl <<
         endl;
    if (disp) {
        cerr << "Результат второй модификации";
        cerr << endl << "Запаздывающие требования: ";
        for (auto it : secondResult.second)
            cerr << it + 1 << " ";

        cerr << endl << "Незапаздывающие требования: ";
        for (auto it : secondResult.first)
            cerr << it + 1 << " ";
        cerr << endl<<"Сумма весов запаздывающих требований: " << F(secondResult.second) <<
             endl << endl;
    }
}
random_device rd;

int gen_num(int l, int r)
{
    return l + rd()%(r-l + 1);
}
void generate_data(int count, int LborderR, int RborderR, int LborderD, int RborderD, int LborderW, int RborderW) // генерация t,r,d,p,w
{
    n = count;
    t = rd() % 10;
    r.resize(n);
    d.resize(n);
    p.resize(n);
    w.resize(n);
    for (int i = 0; i < n; i++) {
        d[i] = p[i] = w[i] = r[i] = 0;
        r[i] = gen_num(LborderR,RborderR);
        if (r[i]+1>RborderD)
            r[i]--;
        d[i] = gen_num(r[i]+1,RborderD);
        while (d[i] <= r[i])
            d[i] = gen_num(LborderD,RborderD);
        w[i] =  gen_num(LborderW,RborderW);
    }

    sort(d.begin(), d.end());
    sort(r.begin(), r.end());
    for (int i = 0; i < n; i++)
        p[i] = rd() % (d[i] - r[i]) + 1;
    sort(d.begin(), d.end());
}
int best[2];
double min_sootn[2];
double max_sootn[2];
void solveandcompare(int disp, ostream &cout) {
    auto firstResult = FirstModification();
    cout << "Результат первой модификации";
    cout << endl << "Запаздывающие требования: ";
    for (auto elem : firstResult.second)
        cout << elem + 1 << " ";

    cout << endl << "Незапаздывающие требования: ";
    for (auto elem : firstResult.first)
        cout << elem + 1 << " ";

    cout << endl << "Сумма весов запаздывающих требований: " << F(firstResult.second) << endl << endl;
    if (disp) {
        cerr << "Результат первой модификации" << endl;
        cerr << "Запаздывающие требования: ";
        for (auto it : firstResult.second)
            cerr << it + 1 << " ";

        cerr << endl << "Незапаздывающие требования: ";
        for (auto it : firstResult.first)
            cerr << it + 1 << " ";
        cerr << endl << "Сумма весов запаздывающих требований: " << F(firstResult.second) <<
             endl << endl;
    }
    auto secondResult = SecondModification();
    cout << "Результат второй модификации";

    cout << endl << "Запаздывающие требования: ";
    for (auto it : secondResult.second)
        cout << it + 1 << " ";

    cout << endl << "Незапаздывающие требования: ";
    for (auto it : secondResult.first)
        cout << it + 1 << " ";

    cout << endl << "Сумма весов запаздывающих требований: " << F(secondResult.second) << endl <<
         endl;
    if (disp) {
        cerr << "Результат второй модификации";
        cerr << endl << "Запаздывающие требования: ";
        for (auto it : secondResult.second)
            cerr << it + 1 << " ";

        cerr << endl << "Незапаздывающие требования: ";
        for (auto it : secondResult.first)
            cerr << it + 1 << " ";
        cerr << endl << "Сумма весов запаздывающих требований: " << F(secondResult.second) <<
             endl << endl;
    }

    int first = F(firstResult.second);
    int second = F(secondResult.second);
    if (first <= second) {
        best[0]++;
    }
    if (second <= first) {
        best[1]++;
    }
    if (first != 0 && second != 0) {
        min_sootn[0] = min(min_sootn[0], first * 1.0 / second);
        max_sootn[0] = max(max_sootn[0], first * 1.0 / second);

        min_sootn[1] = min(min_sootn[1], second * 1.0 / first);
        max_sootn[1] = max(max_sootn[1], second * 1.0 / first);
    }
}
void Compare_Modifications(ofstream &fout) {
    cerr << "Введите количество задач, на которых будут сравниваться алгоритмы: ";
    int tests;
    cin >> tests;
    cerr << "Введите n: ";
    int count;
    cin >> count;
    int rborderR, rborderD, rborderW;
    int lborderR, lborderD, lborderW;
    cerr << "Введите нижнюю и верхнюю границу r_i: ";
    cin >> lborderR >> rborderR;
    cerr << "Введите нижнюю и верхнюю границу d_i: ";
    cin >> lborderD >> rborderD;
    cerr << "Введите нижнюю и верхнюю границу w_i: ";
    cin >> lborderW >> rborderW;
    int disp = 2;
    while (disp != 0 && disp != 1) {
        cerr << "Для просмотра решения каждого примера нажмите 1, иначе 0: ";
        cin >> disp;
    }

    best[0] = best[1] = 0;
    max_sootn[0] = max_sootn[1] = 0;
    min_sootn[0] = min_sootn[1] = 1e9;

    for (int i = 0; i < tests; i++) {
        generate_data(count, lborderR, rborderR, lborderD, rborderD, lborderW, rborderW);
        display(fout);
        if (disp)
            display(cerr);
        solveandcompare(disp, fout);
    }
    cerr << fixed << setprecision(2) << "Первая модификация не хуже второй в " << best[0] * 100.0 / tests << " % задач"
         << endl;
    cerr << fixed << setprecision(2) << "Вторая модификация не хуже первой в " << best[1] * 100.0 / tests << " % задач"
         << endl;
    fout << fixed << setprecision(2) << "Первая модификация не хуже второй в " << best[0] * 100.0 / tests << " % задач"
         << endl;
    fout << fixed << setprecision(2) << "Вторая модификация не хуже первой в " << best[1] * 100.0 / tests << " % задач"
         << endl;


    cerr << fixed << setprecision(2) << "Минимальное соотношение первой модификации ко второй " << min_sootn[0] << endl;
    cerr << fixed << setprecision(2) << "Максимальное соотношение первой модификации ко второй " << max_sootn[0]
         << endl;
    cerr << fixed << setprecision(2) << "Минимальное соотношение второй модификации к первой " << min_sootn[1] << endl;
    cerr << fixed << setprecision(2) << "Максимальное соотношение второй модификации к первой " << max_sootn[1] << endl;


    fout << fixed << setprecision(2) << "Минимальное соотношение первой модификации ко второй " << min_sootn[0] << endl;
    fout << fixed << setprecision(2) << "Максимальное соотношение первой модификации ко второй " << max_sootn[0]
         << endl;
    fout << fixed << setprecision(2) << "Минимальное соотношение второй модификации к первой " << min_sootn[1] << endl;
    fout << fixed << setprecision(2) << "Максимальное соотношение второй модификации к первой " << max_sootn[1] << endl;


    if (best[0] > best[1]) {
        double proc = 100;
        if (best[1]) {
            proc = best[0] * 1.0 / best[1];
        }
        cerr
                << "Для заданных ограничений лучше выбрать первую модификацию, так как она отработала лучше второй модификации в "
                << proc << "% задач" << endl;
        fout
                << "Для заданных ограничений лучше выбрать первую модификацию, так как она отработала лучше второй модификации в "
                << proc << "% задач" << endl;

    } else {
        double proc = 100;
        if (best[0]) {
            proc = best[1] * 1.0 / best[0];
        }

        cerr
                << "Для заданных ограничений лучше выбрать вторую модификацию, так как она отработала лучше первой модификации в "
                <<
                proc << "% задач" << endl;

        fout
                << "Для заданных ограничений лучше выбрать вторую модификацию, так как она отработала лучше первой модификации в "
                <<
                proc << "% задач" << endl;

    }
}


int main()
{
    ofstream fout("result.txt");
    bool ok = true;
    while (ok) {
        int choise = -1;
        while (choise < 0 || choise > 3) {
            cerr << "Введите 1 для ввода данных с файла" << endl;
            cerr << "2 для ввода данных с консоли" << endl;
            cerr << "3 для сравнения модификаций" << endl;
            cerr << "0 для выхода из программы" << endl;
            cin >> choise;

        }
        switch (choise) {
            case 1: {
                cerr << "Введите путь к файлу: ";
                string path;
                cin >> path;
                if (!FileInput(path)) {
                    cerr << "Не удалось открыть файл или неверные входные данные в файле" << endl;
                } else {
                    display(cerr);
                    solve(1, fout);
                }
                break;
            }
            case 2: {
                ConsoleInput();
                solve(1, fout);
                break;
            }
            case 3:{
                Compare_Modifications(fout);
                break;
            }
            case 0: {
                ok = false;
                break;
            }
        }
    }
}