Untitled

mail@pastecode.io avatar
unknown
c_cpp
3 years ago
5.1 kB
2
Indexable
Never
#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <string.h>

int arraySize;
int heapSize;
int auxSize;
int casos = 0;

class heapBinary {
public:
  int cases;
  int id;

  int parentof(int pos) { return floor((pos - 1) / 2); }
  int leftChild(int pos) { return 2 * pos + 1; }
  int rightChild(int pos) { return 2 * pos + 2; }

  void heapBuild(int aux[]) {
    int lastnonLeaf = floor(heapSize / 2) - 1;
    for (int i = lastnonLeaf; i >= 0; i--)
      this->bubbleDown(i, aux);
  }

  heapBinary() {}

  void swap(int pos1, int pos2,
            int aux[]) { // pos1 is the node to be swapped, pos2 is the last
                         // node, or maybe other node
    aux[this[pos1].id] = pos2;

    aux[this[pos2].id] = pos1;

    heapBinary heapTemp = this[pos1];
    this[pos1] = this[pos2];
    this[pos2] = heapTemp;
  }

  int bubbleDown(int pos, int aux[]) {
    int rChild = this->rightChild(pos);
    int lChild = this->leftChild(pos);
    int parent = pos;
    int trigger = 0;
    if (lChild < heapSize) {
      if ((this[lChild].cases > this[parent].cases) ||
          ((this[lChild].cases == this[parent].cases) &&
           (this[lChild].id > this[parent].id))) {
        parent = lChild;
        trigger = 1;
      }
      if (rChild < heapSize) {
        if ((this[rChild].cases > this[parent].cases) ||
            ((this[rChild].cases == this[parent].cases) &&
             (this[rChild].id > this[parent].id))) {
          parent = rChild;
          trigger = 1;
        }
      }
    }
    if (trigger) {
      this->swap(pos, parent, aux);
      return this->bubbleDown(parent, aux);
    }
    return 1; // useless
  }

  void bubbleUp(int pos, int aux[]) {
    int position2 = pos;
    heapBinary c1;
    heapBinary c2;
    while (position2 = this->parentof(position2),
           (pos > 0) && (this[pos].cases >= this[position2].cases)) {
      c1 = this[pos];
      c2 = this[position2];
      if (((c1.cases == c2.cases) && (c1.id > c2.id)) ||
          (c1.cases > c2.cases)) {
        this->swap(pos, position2, aux);
        pos = position2;
      }
    }
  }

  void heapInsert(int newid, int newcases, int aux[]) {
    this[heapSize].cases = newcases;
    this[heapSize].id = newid;
    casos += newcases;
    this->bubbleUp(heapSize, aux);
    heapSize++;
  }

  void heapExtract(int pos, int aux[]) { // pos is the node to be swapped
    casos -= this[pos].cases;
    this[pos].cases = -1;
    this->swap(pos, heapSize - 1, aux); // pos swaps with last node
    heapSize--;
    this->bubbleDown(pos, aux);
  }
};

void duplicate(heapBinary **add, int **arr) {
  arraySize *= 2;
  int *newArray = new int[arraySize];
  heapBinary *heap2 = new heapBinary[arraySize];
  for (int i = 0; i < auxSize; i++) {
    heap2[i] = *((add[0] + i));
    newArray[i] = *((arr[0] + i));
  }
  delete[] * add;
  delete[] * arr;
  *add = heap2;
  *arr = newArray;
}

int main() {
  std::string choice;
  std::string param1;
  std::string param2;
  int N;
  std::cin >> N;
  arraySize = auxSize = N;
  heapSize = N;
  int *auxArray = new int[N];
  heapBinary *hospitais = new heapBinary[N];
  for (int i = 0; i < N; i++) {
    std::cin >> hospitais[i].cases;
    hospitais[i].id = i;
    auxArray[i] = i;
    casos += hospitais[i].cases;
  }
  hospitais->heapBuild(auxArray);

  while (std::cin >> choice, choice != "END", std::cin >> param1) {

    if (choice == "NEW") {
      std::cin >> param2;
      if (auxSize == arraySize)
        duplicate(&hospitais, &auxArray);
      auxArray[auxSize] = heapSize;
      auxSize++;
      hospitais->heapInsert(std::stoi(param1), std::stoi(param2), auxArray);
      std::cout << std::to_string(hospitais[0].id) << " "
                << std::to_string(hospitais[0].cases) << std::endl;
    } else if (choice == "DEL") {
      int indexH = auxArray[std::stoi(param1)];
      hospitais->heapExtract(indexH, auxArray);

      std::cout << std::to_string(hospitais[0].id) << " "
                << std::to_string(hospitais[0].cases) << std::endl;

    } else if (choice == "IN") {
      std::cin >> param2;
      int indexH = auxArray[stoi(param1)];
      hospitais[indexH].cases += stoi(param2);
      casos += stoi(param2);
      hospitais->bubbleUp(indexH, auxArray);
      std::cout << std::to_string(hospitais[auxArray[stoi(param1)]].cases)
                << std::endl;

    } else if (choice == "OUT") {
      std::cin >> param2;
      int indexH = auxArray[stoi(param1)];
      hospitais[indexH].cases -= stoi(param2);
      casos -= stoi(param2);
      hospitais->bubbleDown(indexH, auxArray);
      std::cout << std::to_string(hospitais[auxArray[stoi(param1)]].cases)
                << std::endl;

    } else if (choice == "PAY") {
      int resources = stoi(param1);
      int howMany = 0;
      while ((resources-- > 0) && (hospitais[0].cases > 0)) {
        hospitais[0].cases -= 1;
        casos -= 1;
        hospitais->bubbleDown(0, auxArray);
        howMany++;
      }
      std::cout << std::to_string(howMany) << std::endl;
    }
  }
  delete[] hospitais;
  delete[] auxArray;
  std::cout << std::to_string(casos) << std::endl;
}