РАБОАТЕТ файл

#include <iostream>
#include <vector>
using namespace std;
#include <fstream>

enum sort_type
{
    heap_max = 0,
    heap_min = 1
};

struct heap_elements
{
    int value;
    int own_ID;
};

bool operator<(const heap_elements& a, const heap_elements& b)
{
    return (a.value < b.value);
}

class Heap
{
    std::vector<struct heap_elements> h;
    int heap_size;

public:
    Heap();
    bool isempty();
    heap_elements get_top();
    void siftup(int sort_type, int pos, std::vector<int>& ID_to_Index);
    void siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index);
    void swap(int i, int j, std::vector<int>& ID_to_Index);
    void add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index);
    void delete_vertex(int sort_type,  int ID, std::vector<int>& ID_to_Index);
    void out();
    void outHeap();
    void print_vector(std::vector<int>& vector);
};

Heap::Heap()
{
    std::vector<struct heap_elements> h;
    heap_size = 0;
}

heap_elements Heap::get_top()
{
    return h[0];
}

bool Heap::isempty()
{
    if (heap_size == 0)
        return true;
    return false;
}

void Heap::swap(int i, int j, std::vector<int>& ID_to_Index)
{
    heap_elements buff;
    buff = h[i];
    h[i] = h[j];
    h[j] = buff;

    ID_to_Index[h[i].own_ID] = i; //На местах в этом массиве лежат айди этой кучи все ок
    ID_to_Index[h[j].own_ID] = j;
}

void Heap::siftup(int sort_type, int pos, std::vector<int>& ID_to_Index)
{
    int curr = pos;
    int parent = (curr - 1) / 2;
    while (curr > 0 & parent >= 0)
    {
        if (sort_type == heap_max & h[parent] < h[curr])
            swap(parent, curr, ID_to_Index);

        if (sort_type == heap_min & h[curr] < h[parent])
            swap(parent, curr, ID_to_Index);

        curr = parent;
        parent = (curr - 1) / 2;
    }
}

void Heap::outHeap() {
  int i = 0;
  int k = 1;
  while(i < heap_size) {
    while((i < k) && (i < heap_size)) {
      cout << h[i].value << " ";
      i++;
    }
    cout << endl;
    k = k * 2 + 1;
  }
}

void Heap::siftdown(int sort_type, int pos, std::vector<int>& ID_to_Index)
{

    int parent, max_child, min_child;

    int curr = pos;
    int child_l = 2 * curr + 1;
    int child_r = 2 * curr + 2;

    while (child_l < heap_size)
    {
        cout << "child_l < heap_size:" << child_l << "< " << heap_size << endl;
        if (sort_type == heap_max)
        {
            if (child_l == heap_size - 1)
                max_child = child_l;
            else if (h[child_r] < h[child_l])
                max_child = child_l;
            else
                max_child = child_r;

            if (h[curr] < h[max_child])
                swap(curr, max_child, ID_to_Index);

            curr = max_child;
            child_l = 2 * curr + 1;
            child_r = 2 * curr + 2;
        }

        if (sort_type == heap_min)
        {
            cout << "sort_type == heap_min" << endl;
            if (child_l == heap_size - 1)
                min_child = child_l;
            else if (h[child_r] < h[child_l])
                min_child = child_r;
            else
                min_child = child_l;

            cout << "min_child = " << min_child << endl;
            if (h[min_child] < h[curr]) {
                cout << "min_child, curr " << min_child << " " << curr << endl;
                cout << "h[min_child] < h[curr]: " << h[min_child].value << " < " << h[curr].value << endl;
                swap(curr, min_child, ID_to_Index);
            }
            curr = min_child;
            child_l = 2 * curr + 1;
            child_r = 2 * curr + 2;
        }
    }
}

void Heap::print_vector(std::vector<int>& vector)
{
    if (vector.size() == 0)
        cout << "None " << endl;
    else {
        cout << "vector: ";
        for (int i = 0; i < vector.size() - 1; i++)
            cout << vector[i] << ", ";
        cout << vector[vector.size() - 1] << ";" << endl;
    }
}

void Heap::add(int sort_type, int ID, int value, std::vector<int>& ID_to_Index)
{
    heap_elements vertex;
    vertex.value = value;
    vertex.own_ID = ID;

    h.push_back(vertex);


    //Если это новое добавление, то надо делать пушбек,
    //а если старое, то надо просто на место ID написать heap_size
    cout << "Сейчас будем добавлять. Но новый или старый?" << endl;
    cout << "ID_to_Index.size() = "  << ID_to_Index.size() << endl;
    cout << "heap_size = "  << heap_size << endl;
    cout << "ID = "  << ID << endl;

    if (ID < ID_to_Index.size()) {
        cout << "Значит это старый, ID_to_Index до" << endl;
        print_vector(ID_to_Index);
        ID_to_Index[ID] = heap_size;
        cout << "After";
        print_vector(ID_to_Index);
    }
    else {
        cout << "Значит это новый, ID_to_Index до" << endl;
        print_vector(ID_to_Index);
        ID_to_Index.push_back(heap_size); //должно быть общее у двух куч
        cout << "After";
        print_vector(ID_to_Index);
    }
    heap_size++;
    siftup(sort_type, heap_size-1, ID_to_Index);
}

void Heap::delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index)
{

    int pos = ID_to_Index[ID];

    cout << "Вызвали удаление, ID = " << ID << endl;
    cout << "pos = " << pos << endl;
    print_vector(ID_to_Index);



    swap(pos, heap_size - 1, ID_to_Index); //Можно не делать свап
    h.pop_back();
    heap_size--;
    ID_to_Index[ID] = -1; //мб убрать

    int parent = (pos - 1) / 2;

    if (sort_type == heap_min)
    {
        if (h[pos] < h[parent])
            siftup(sort_type, pos, ID_to_Index);
        else
            siftdown(sort_type, pos, ID_to_Index);
    }

    if (sort_type == heap_max)
    {
        if (h[parent] < h[pos])
            siftup(sort_type, pos, ID_to_Index);
        else
            siftdown(sort_type, pos, ID_to_Index);
    }

}

void Heap::out(void)
{
    if (heap_size == 0)
        cout << "heap: None " << endl;
    else
    {
        cout << "heap: ";
        for (int i = 0; i < heap_size - 1; i++)
            cout << h[i].value << ", ";

        cout << h[heap_size - 1].value << ";" << endl;
    }
}

void print_vector(std::vector<int>& vector)
{
    cout << "vector: ";
    for (int i = 0; i < vector.size() - 1; i++)
        cout << vector[i] << ", ";
    cout << vector[vector.size() - 1] << ";" << endl;
}


int main()
{


    ifstream ifs("com.txt");
    ofstream out("results.txt");
    int count_tests;
    ifs >> count_tests;

    for (int k = 0; k < count_tests; k++)
    {

        Heap heap1;
        Heap heap2;

        std::vector<int> ID_to_Index;
        int NumberHeap;
        int curr_ID = 0;
        char c;

        int N, M, K, ID, ID_root1, root2_ID, ID_root2, count = 1;
        ifs >> N;
        ifs >> M;
        int answers[M];
        K = 3;
        int R = 0, L = 0;
        int a[N];
        for (int j = 0; j < N; j++)
            ifs >> a[j];

        int ID_to_HeapNumber[N]; //При перебрасывании в другую кучу

        heap1.add(heap_max, curr_ID, a[0], ID_to_Index);
        ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
        curr_ID++;
        heap1.out();
        heap2.outHeap();

        for (int i = 0; i < M; ++i)
        {
            cout << "-------------------------------ЗАПРОС НОМЕР " << i
                 << "-----------------------------------------" << endl;
            // cin >> c;
            ifs >> c;

            if (c == 'R')
            {
                count++;
                R++;

                cout << "R; R = " << R << " count =" << count << endl;

                if (count < K)
                {
                    cout << "count < K, просто добавляю в кучу1" << endl;

                    heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
                    ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
                    curr_ID++;

                    cout << "--------------------ANSWER--------------: "
                         << "-1" << endl;
                    answers[i] = -1;

                    heap1.out();
                    heap2.outHeap();
                }

                if (count == K)
                {
                    cout << "count == K, просто добавляю в кучу" << endl;

                    heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
                    ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
                    curr_ID++;

                    cout << "--------------------ANSWER--------------: " << heap1.get_top().value
                         << endl;
                    answers[i] = heap1.get_top().value;
                    heap1.out();
                    heap2.outHeap();
                }

                if (count > K)
                {
                    cout << "count > K, Появились лишние - Надо решить куда кидать" << endl;

                    if (a[R] > heap1.get_top().value)
                    {
                        cout << "a[R] > корня - во 2 кучу просто" << endl;

                        heap2.add(heap_min, curr_ID, a[R], ID_to_Index);
                        ID_to_HeapNumber[curr_ID] = 2; //Обновляю ID_to_HeapNumber
                        curr_ID++;

                        cout << "--------------------ANSWER--------------: "
                             << heap1.get_top().value << endl;
                        answers[i] = heap1.get_top().value;
                        heap1.out();
                        heap2.outHeap();
                    }

                    if (a[R] <= heap1.get_top().value)

                    {
                        cout << "a[R] <= корня - корень во 2 кучу  " << endl;

                        heap_elements root1, root2;

                        //Запоминаю корень 1 кучи
                        root1 = heap1.get_top();
                        ID_root1 = root1.own_ID;

                        cout << "удаляю корень 1 кучи из 1 кучи" << endl;
                        // удаляю корень 1 кучи из 1 кучи
                        heap1.delete_vertex(heap_max, ID_root1, ID_to_Index);
                        heap1.out();
                        heap2.outHeap();

                        cout << "Добавляю корень 1 кучи во 2 кучу не меняя ID" << endl;
                        // Добавляю корень 1 кучи во 2 кучу не меняя ID
                        heap2.add(heap_min, ID_root1, root1.value, ID_to_Index);
                        ID_to_HeapNumber[ID_root1] = 2; //Обновляю ID_to_HeapNumber
                        heap1.out();
                        heap2.outHeap();


                        cout << "Добавляю в 1 кучу a[R]  меняя айди" << endl;
                        //Добавляю в 1 кучу a[R]  меняя айди
                        heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
                        ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
                        curr_ID++;
                        heap1.out();
                        heap2.outHeap();
                        answers[i] = heap1.get_top().value;
                        cout << "--------------------ANSWER--------------: "
                             << heap1.get_top().value << endl;
                    }
                }
            }
            else
            {
                L++;
                count--;

                cout << "L,count = " << L << " " << count << endl;

                cout << "Удаляем a[L-1]" << endl;

                ID = L - 1;
                NumberHeap = ID_to_HeapNumber[ID];

                cout << "NumberHeap = " << NumberHeap << endl;

                cout << " Если лежит в куче1 то удаляем там, иначе во 2 " << endl;
                //Если лежит в куче1 то удаляем там, иначе во 2
                if (NumberHeap == 1)
                    heap1.delete_vertex(heap_max, ID, ID_to_Index);
                else
                    heap2.delete_vertex(heap_min, ID, ID_to_Index);

                heap1.out();
                heap2.outHeap();

                if (count >= K)
                {
                    cout << "count >= K; В 1 куче к-1, во 2 не пусто" << endl;


                    //Если удалили из 2 кучи, то первая не пострадала и просто принтим
                    if (NumberHeap == 2)
                    {
                        cout << "удалили из 2 кучи, то первая не пострадала и просто принтим "
                             << endl;
                        cout << "--------------------ANSWER--------------: "
                             << heap1.get_top().value << endl;
                        answers[i] = heap1.get_top().value;
                    }

                    else
                    {
                        cout << "удалили из 1 кучи - надо восстановить баланс";
                        //Запоминаю вершину кучи2
                        heap_elements root2 = heap2.get_top();
                        root2_ID = root2.own_ID;

                        cout << "//Удаляем вершину кучи2, т.к. она будет в куче1" << endl;
                        //Удаляем вершину кучи2, т.к. теперь она в куче1
                        heap2.delete_vertex(heap_min, root2_ID, ID_to_Index);
                        heap1.out();
                        heap2.outHeap();

                        cout
                            << "Добавляем вершину кучи2 в кучу1  не меняя индекс чтобы стало K штук"
                            << endl;
                        //Добавляем вершину кучи2 в кучу1  не меняя индекс чтобы стало K штук
                        heap1.add(heap_max, root2_ID, root2.value, ID_to_Index);
                        ID_to_HeapNumber[root2_ID] = 1; //Обновляю ID_to_HeapNumber

                        cout << "--------------------ANSWER--------------: "
                             << heap1.get_top().value << endl;
                        answers[i] = heap1.get_top().value;
                        heap1.out();
                        heap2.outHeap();
                    }
                }
                else
                {
                    cout << "--------------------ANSWER--------------: -1 " << endl;
                    answers[i] = -1;
                }
            }
        }

        cout << endl;
        int y;
        int true_ans[M];
        for (int j = 0; j < M; j++)
        {
            cout << answers[j] << " ";
            out << answers[j] << " ";
        }
        out << endl;
        for (int j = 0; j < M; j++)
        {
            ifs >> y;
            true_ans[j] = y;
            out << y << " ";
        }
        out << endl;
        for (int j = 0; j < M; j++)
        {
            if (true_ans[j] != answers[j])
                out << "WA" << j << " ";
            else
                out << "1 ";
        }
        out << endl;
    }


    return 0;
}