Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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, 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();
- };
- 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, std::vector<int>& ID_to_Index)
- {
- int curr = heap_size - 1;
- 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::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;
- // max_child = (h[child_r] < h[child_l]) ? child_l : child_r;
- // min_child = (h[child_r] > h[child_l]) ? child_l : child_r;
- /*
- if (h[child_r] < h[child_l])
- max_child = child_l;
- else
- max_child = child_r;
- */
- while (child_l < heap_size)
- {
- 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)
- {
- 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;
- if (h[min_child] < h[curr])
- swap(curr, min_child, ID_to_Index);
- curr = min_child;
- child_l = 2 * curr + 1;
- child_r = 2 * curr + 2;
- }
- }
- }
- 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
- if (ID < ID_to_Index.size()) {
- ID_to_Index[ID] = heap_size;
- }
- else {
- ID_to_Index.push_back(heap_size); //должно быть общее у двух куч
- }
- heap_size++;
- siftup(sort_type, ID_to_Index);
- }
- void Heap::delete_vertex(int sort_type, int ID, std::vector<int>& ID_to_Index)
- {
- int pos = ID_to_Index[ID];
- swap(pos, heap_size - 1, ID_to_Index); //Можно не делать свап
- h.pop_back();
- heap_size--;
- ID_to_Index[ID] = -1; //мб убрать
- siftdown(sort_type, pos, ID_to_Index);
- }
- 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 = 5;
- 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++;
- for (int i = 0; i < M; ++i)
- {
- // cin >> c;
- ifs >> c;
- if (c == 'R')
- {
- count++;
- R++;
- if (count < K)
- {
- heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
- ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
- curr_ID++;
- answers[i] = -1;
- }
- if (count == K)
- {
- heap1.add(heap_max, curr_ID, a[R], ID_to_Index);
- ID_to_HeapNumber[curr_ID] = 1; //Обновляю ID_to_HeapNumber
- curr_ID++;
- answers[i] = heap1.get_top().value;
- }
- if (count > K)
- {
- if (a[R] > heap1.get_top().value)
- {
- heap2.add(heap_min, curr_ID, a[R], ID_to_Index);
- ID_to_HeapNumber[curr_ID] = 2; //Обновляю ID_to_HeapNumber
- curr_ID++;
- answers[i] = heap1.get_top().value;
- }
- if (a[R] <= heap1.get_top().value)
- {
- heap_elements root1, root2;
- //Запоминаю корень 1 кучи
- root1 = heap1.get_top();
- ID_root1 = root1.own_ID;
- // удаляю корень 1 кучи из 1 кучи
- heap1.delete_vertex(heap_max, ID_root1, ID_to_Index);
- // Добавляю корень 1 кучи во 2 кучу не меняя ID
- heap2.add(heap_min, ID_root1, root1.value, ID_to_Index);
- ID_to_HeapNumber[ID_root1] = 2; //Обновляю ID_to_HeapNumber
- //Добавляю в 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++;
- answers[i] = heap1.get_top().value;
- }
- }
- }
- else
- {
- L++;
- count--;
- ID = L - 1;
- NumberHeap = ID_to_HeapNumber[ID];
- //Если лежит в куче1 то удаляем там, иначе во 2
- if (NumberHeap == 1)
- heap1.delete_vertex(heap_max, ID, ID_to_Index);
- else
- heap2.delete_vertex(heap_min, ID, ID_to_Index);
- if (count >= K)
- {
- //Если удалили из 2 кучи, то первая не пострадала и просто принтим
- if (NumberHeap == 2)
- {
- answers[i] = heap1.get_top().value;
- }
- else
- {
- //Запоминаю вершину кучи2
- heap_elements root2 = heap2.get_top();
- root2_ID = root2.own_ID;
- //Удаляем вершину кучи2, т.к. теперь она в куче1
- heap2.delete_vertex(heap_min, root2_ID, ID_to_Index);
- //cout
- //Добавляем вершину кучи2 в кучу1 не меняя индекс чтобы стало K штук
- heap1.add(heap_max, root2_ID, root2.value, ID_to_Index);
- ID_to_HeapNumber[root2_ID] = 1; //Обновляю ID_to_HeapNumber
- answers[i] = heap1.get_top().value;
- }
- }
- else
- {
- answers[i] = -1;
- }
- }
- }
- cout << endl;
- int y;
- int true_ans[M];
- /*
- for (int j = 0; j < M; 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 << " ";
- cout << "Неверный ответ на тесте " << k << endl;
- }
- else
- out << "1 ";
- }
- out << endl;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment