#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;
    }
}

void generate_data(int count, int RboderR, int RborderD, int RborderW) // генерация t,r,d,p,w
{
    random_device rd;
    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] = rd() % RboderR;
        d[i] = rd() % RborderD;
        while (d[i] <= r[i])
            d[i] = rd() % RborderD + 1;
        w[i] = rd() % 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];

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]++;
    }
}

void Compare_Modifications(ofstream &fout) {
    cerr << "Введите количество задач, на которых будут сравниваться алгоритмы: ";
    int tests;
    cin >> tests;
    cerr << "Введите n: ";
    int count;
    cin >> count;
    int rboderR, rborderD, rborderW;
    cerr << "Введите максимальную границу r_i: ";
    cin >> rboderR;
    cerr << "Введите максимальную границу d_i: ";
    cin >> rborderD;
    cerr << "Введите максимальную границу w_i: ";
    cin >> rborderW;
    int disp = 2;
    while (disp != 0 && disp != 1) {
        cerr << "Для просмотра решения каждого примера нажмите 1, иначе 0: ";
        cin >> disp;
    }

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

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;
            }
        }
    }
}