daily pastebin goal
67%
SHARE
TWEET

Untitled

a guest May 16th, 2018 97 in 7 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <limits.h>
  3. using namespace std;
  4. #pragma region FunctionsDelcaration
  5. struct Node {
  6.     unsigned short indexToPrint;
  7.     unsigned int value;
  8. };
  9. void TrickleDown(int i, int Heapsize, Node tab[]);
  10. void TrickleDownMin(int i, int Heapsize, Node tab[]);
  11. void TrickleDownMax(int i, int Heapsize, Node tab[]);
  12. void BubbleUp(int i, Node tab[]);
  13. void BubbleUpMin(int i, Node tab[]);
  14. void BubbleUpMax(int i, Node tab[]);
  15. bool isOnMaxLevel(int index);
  16. void swap(int child, int parent, Node tab[]);
  17. void removeFromHeap(Node tab[], int &heapSize, int index);
  18. void CollatzMax(Node tab[], int &heapsize);
  19. void CollatzMin(Node tab[], int &heapsize);
  20. //////////////////////////////////////////////////////////////////////
  21. int getGrandparent(int grandchild);
  22. int getParent(int child);
  23. int getLeftChild(int parent);
  24. int getRightChild(int parent);
  25. int getGrandchild1(int child);
  26. int getGrandchild2(int child);
  27. int getGrandchild3(int child);
  28. int getGrandchild4(int child);
  29. bool hasParent(int child);
  30. bool isChild(int child, int parent);
  31. bool hasGrandparent(int i);
  32. bool hasChildren(int i, int HeapSize);
  33. int GetIndexOfSmallestOfChildrenAndGrandchildren(int i, int HeapSize, Node tab[]);
  34. int GetIndexOfBiggestOfChildrenAndGrandchildren(int i, int HeapSize, Node tab[]);
  35. #pragma endregion
  36. int main() {
  37. #pragma region input
  38.     unsigned short howManyExeComm, startingHeapSize, howManyCommands;
  39.     char command;
  40.     cin >> startingHeapSize;
  41.     int heapSize = startingHeapSize;
  42.     unsigned int *liczby = new unsigned int[startingHeapSize];
  43.     for (int i = 0; i < startingHeapSize; i++) {
  44.         cin >> liczby[i];
  45.         if (liczby[i] == 1) heapSize--;
  46.     }
  47.     int *tabZJedynkami = new int[startingHeapSize - heapSize];
  48.     Node* tab = new Node[heapSize];
  49.     int ileJedynek = 0;
  50.     int a = 0;
  51.     for (int j = 0; j < startingHeapSize; j++)
  52.     {
  53.         if (liczby[j] != 1) {
  54.             a = j - ileJedynek;
  55.             tab[a].value = liczby[j];
  56.             tab[a].indexToPrint = j;
  57.             BubbleUp(a, tab);
  58.         }
  59.         else {//liczby[j]==1
  60.             tabZJedynkami[ileJedynek] = j;
  61.             ileJedynek++;
  62.         }
  63.     }
  64.  
  65. #pragma endregion
  66. #pragma region proceeding
  67.     cin >> howManyCommands;
  68.         /*
  69.         cout << "Tablica z jedynkami: "<<endl;
  70.         for (size_t i = 0; i < startingHeapSize-heapSize; i++)
  71.         cout << "IndexToPrint: " << tabZJedynkami[i] << " wartosc: " << 1 << " " << endl;
  72.  
  73.         cout << "Heap tuz po zbudowaniu: "<<endl;
  74.         for (size_t i = 0; i < heapSize; i++)
  75.         cout << "IndexToPrint: " << tab[i].indexToPrint << " wartosc: " << tab[i].value << " " << endl;
  76.         */
  77.     while (howManyCommands--) {
  78.         cin >> howManyExeComm >> command;
  79.         if (command == 's') {
  80.             for (size_t j = 0; j < howManyExeComm; j++) {
  81.                 CollatzMin(tab, heapSize);
  82.                 /*unsigned int* liczbyTemp = new unsigned int[startingHeapSize];
  83.  
  84.                 for (int i = 0; i < startingHeapSize - ileJedynek; i++)
  85.                 liczbyTemp[tab[i].indexToPrint] = tab[i].value;
  86.                 for (size_t i = 0; i < ileJedynek; i++) {
  87.                 liczbyTemp[tabZJedynkami[i]] = 1;
  88.                 }
  89.                 for (int i = 0; i < startingHeapSize; i++) {
  90.                 cout << "IndexToPrint: " << liczby[i] << " wartosc: " << tab[i].value << " " << endl;
  91.                 }
  92.                 delete[] liczbyTemp;
  93.                 */
  94.             }
  95.         }
  96.         else if (command == 'l') {
  97.             for (size_t i = 0; i < howManyExeComm; i++) {
  98.                 CollatzMax(tab, heapSize);
  99.                 /*unsigned int* liczbyTemp = new unsigned int[startingHeapSize];
  100.  
  101.                 for (int i = 0; i < startingHeapSize - ileJedynek; i++)
  102.                 liczbyTemp[tab[i].indexToPrint] = tab[i].value;
  103.                 for (size_t i = 0; i < ileJedynek; i++) {
  104.                 liczbyTemp[tabZJedynkami[i]] = 1;
  105.                 }
  106.                 for (int i = 0; i < startingHeapSize; i++) {
  107.                 cout << "IndexToPrint: " << liczby[i] << " wartosc: " << tab[i].value << " " << endl;
  108.                 }
  109.                 delete[] liczbyTemp;
  110.                 */
  111.             }
  112.         }
  113.     }
  114. #pragma endregion
  115. #pragma region output
  116.     unsigned int* liczbyTemp = new unsigned int[startingHeapSize];
  117.     for (int i = 0; i < startingHeapSize - ileJedynek; i++)
  118.         liczbyTemp[tab[i].indexToPrint] = tab[i].value;
  119.     for (size_t i = 0; i < ileJedynek; i++) {
  120.         liczbyTemp[tabZJedynkami[i]] = 1;
  121.     }
  122.     //cout << endl;
  123.     for (int i = 0; i < startingHeapSize; i++) {
  124.         if (liczbyTemp[i] == 0) cout << "m ";
  125.         else cout << liczbyTemp[i] << ' ';
  126.     }
  127.  
  128.  
  129.  
  130.     //Na stos nie zwalniaj :D
  131.     delete[] liczbyTemp;
  132.     delete[] tabZJedynkami;
  133.     delete[] liczby;
  134.     delete[] tab;
  135. #pragma endregion
  136.     //system("pause");
  137. }
  138.  
  139. void CollatzMin(Node tab[], int &heapsize)
  140. {
  141.     if (heapsize == 0) return;
  142.     if (tab[0].value % 2) { //if odd
  143.         long long b = tab[0].value;
  144.         long long a = 3 * b + 1;
  145.         if (a >= UINT_MAX) {
  146.             tab[0].value = 0;
  147.             removeFromHeap(tab, heapsize, 0);
  148.         }
  149.         else {
  150.             tab[0].value = 3 * tab[0].value + 1;
  151.             TrickleDown(0, heapsize, tab);
  152.         }
  153.     }
  154.     else {  //if even
  155.         tab[0].value /= 2;
  156.         if (tab[0].value == 1)
  157.             removeFromHeap(tab, heapsize, 0);
  158.     }
  159. }
  160. void CollatzMax(Node tab[], int &heapsize)
  161. {
  162.     if (heapsize == 0) return;
  163.     int index;
  164.     if (heapsize == 1) index = 0;
  165.     else if (heapsize == 2) index = 1;
  166.     else if (tab[1].value > tab[2].value) index = 1;
  167.     else if (tab[2].value > tab[1].value) index = 2;
  168.     else index = tab[1].indexToPrint < tab[2].indexToPrint ? 1 : 2;
  169.  
  170.     if (tab[index].value % 2) { //if odd
  171.         long long b = tab[index].value;
  172.         long long a = 3 * b + 1;
  173.         if (a >= UINT_MAX) {
  174.             tab[index].value = 0;
  175.             removeFromHeap(tab, heapsize, index);
  176.         }
  177.         else
  178.             tab[index].value = 3 * tab[index].value + 1;
  179.     }
  180.     else { //if even
  181.         tab[index].value /= 2;
  182.         if (tab[0].value == 1)
  183.             removeFromHeap(tab, heapsize, 0);
  184.         else TrickleDown(index, heapsize, tab);
  185.     }
  186. }
  187.  
  188. #pragma region functions
  189. void TrickleDown(int i, int Heapsize, Node tab[]) { // Odd -> min level //Even -> Max level   ||    i is the position in the array
  190.     if (isOnMaxLevel(i))
  191.         TrickleDownMax(i, Heapsize, tab);
  192.     else
  193.         TrickleDownMin(i, Heapsize, tab);
  194. };
  195. void TrickleDownMin(int i, int Heapsize, Node tab[]) {
  196.     if (hasChildren(i, Heapsize)) {
  197.         int m = GetIndexOfSmallestOfChildrenAndGrandchildren(i, Heapsize, tab);
  198.         if (isChild(m, i)) {//tab[m] is a child of tab[i]]
  199.             if (tab[m].value < tab[i].value || (tab[m].value == tab[i].value && tab[m].indexToPrint<tab[i].indexToPrint))
  200.                 swap(i, m, tab);
  201.             else if (tab[m].value == tab[i].value && tab[m].indexToPrint<tab[i].indexToPrint) {
  202.                 swap(i, m, tab);
  203.             }
  204.         }
  205.         else { //tab[m] is a grandchild of tab[i]]
  206.             if (tab[m].value < tab[i].value || (tab[m].value == tab[i].value && tab[m].indexToPrint<tab[i].indexToPrint)) {
  207.                 swap(i, m, tab);
  208.                 if (tab[m].value > tab[getParent(m)].value || (tab[m].value == tab[getParent(m)].value && tab[m].indexToPrint<tab[getParent(m)].indexToPrint)) {
  209.                     swap(m, getParent(m), tab);
  210.                 }
  211.                 TrickleDownMin(m, Heapsize, tab);
  212.             }
  213.         }
  214.     }
  215. }
  216. void TrickleDownMax(int i, int Heapsize, Node tab[]) {
  217.     if (hasChildren(i, Heapsize)) {
  218.         int m = GetIndexOfBiggestOfChildrenAndGrandchildren(i, Heapsize, tab);
  219.         if (isChild(m, i)) {//tab[m] is a child of tab[i]]
  220.             if (tab[m].value > tab[i].value || (tab[m].value == tab[i].value && tab[m].indexToPrint<tab[i].indexToPrint)) {
  221.                 swap(i, m, tab);
  222.             }
  223.         }
  224.         else { //tab[m] is a grandchild of tab[i]]
  225.             if (tab[m].value > tab[i].value || (tab[m].value == tab[i].value && tab[m].indexToPrint<tab[i].indexToPrint)) {
  226.                 swap(i, m, tab);
  227.                 if (tab[m].value < tab[getParent(i)].value || (tab[m].value == tab[getParent(m)].value && tab[m].indexToPrint<tab[getParent(m)].indexToPrint)) {
  228.                     swap(m, getParent(i), tab);
  229.                 }
  230.                 TrickleDownMax(m, Heapsize, tab);
  231.             }
  232.         }
  233.     }
  234. }
  235. void BubbleUp(int i, Node tab[]) {//i is the position in the array
  236.     if (!isOnMaxLevel(i)) {
  237.         if (hasParent(i)) {
  238.             if (tab[i].value >= tab[getParent(i)].value) {  // IT SHOULD BE > HERE, but test wanted me to do that
  239.                 swap(i, getParent(i), tab);
  240.                 BubbleUpMax(getParent(i), tab);
  241.             }
  242.             else BubbleUpMin(i, tab);
  243.         }
  244.     }
  245.     else //is on MaxLevel
  246.         if (hasParent(i)) {
  247.             if (tab[i].value <= tab[getParent(i)].value) {
  248.                 swap(i, getParent(i), tab);
  249.                 BubbleUpMin(getParent(i), tab);
  250.             }
  251.             else BubbleUpMax(i, tab);
  252.         }
  253.  
  254. };
  255. void BubbleUpMin(int i, Node tab[]) {
  256.     if (hasGrandparent(i) && (tab[i].value < tab[getGrandparent(i)].value)) {
  257.         swap(i, getGrandparent(i), tab);
  258.         BubbleUpMin(getGrandparent(i), tab);
  259.     }
  260. }
  261. void BubbleUpMax(int i, Node tab[]) {
  262.     if (hasGrandparent(i) && tab[i].value > tab[getGrandparent(i)].value) {
  263.         swap(i, getGrandparent(i), tab);
  264.         BubbleUpMax(getGrandparent(i), tab);
  265.     }
  266. }
  267. void removeFromHeap(Node tab[], int &heapSize, int index) {
  268.     heapSize--;
  269.     swap(index, heapSize, tab);
  270.     TrickleDown(index, heapSize, tab);
  271. }
  272. void swap(int child, int parent, Node tab[]) {
  273.     unsigned int temp = tab[child].value;
  274.     int indexTemp = tab[child].indexToPrint;
  275.     tab[child].value = tab[parent].value;
  276.     tab[parent].value = temp;
  277.     tab[child].indexToPrint = tab[parent].indexToPrint;
  278.     tab[parent].indexToPrint = indexTemp;
  279. }
  280. bool isOnMaxLevel(int index) {
  281.     int level = 0, MaxIndex;
  282.     while (true)
  283.     {
  284.         MaxIndex = (int)pow(2.0, level + 1) - 2;
  285.         if (MaxIndex >= index)
  286.         {
  287.             if (level % 2 == 0) return false; //Even Levels are Max
  288.             else return true; //Odd levels are MIN(root is level 1)
  289.         }
  290.         level++;
  291.     }
  292. }
  293. #pragma region getChildren,grandchildren,parent
  294. int getGrandparent(int grandchild) {
  295.     return getParent(getParent(grandchild));
  296. }
  297. int getParent(int child) {
  298.     if (child % 2 == 0)
  299.         return (child / 2) - 1;
  300.     else
  301.         return child / 2;
  302. }
  303. int getLeftChild(int parent) {
  304.     return 2 * parent + 1;
  305. }
  306. int getRightChild(int parent) {
  307.     return 2 * parent + 2;
  308. }
  309. int getGrandchild1(int child) {
  310.     return 2 * (2 * child + 1) + 1;
  311. }
  312. int getGrandchild2(int child) {
  313.     return 2 * (2 * child + 1) + 2;
  314. }
  315. int getGrandchild3(int child) {
  316.     return 2 * (2 * child + 2) + 1;
  317. }
  318. int getGrandchild4(int child) {
  319.     return 2 * (2 * child + 2) + 2;
  320. }
  321. bool hasParent(int child) {
  322.     if (child % 2 == 0) {
  323.         if ((child / 2) - 1 >= 0) return true;
  324.         else return false;
  325.     }
  326.     else {
  327.         if (child / 2 >= 0) return true;
  328.         else return false;
  329.     }
  330. }
  331. bool hasChildren(int i, int HeapSize) {
  332.     if ((i * 2 + 1) < HeapSize) return true;
  333.     else return false;
  334. }
  335. bool hasGrandparent(int i) {
  336.     if (getParent(getParent(i)) >= 0) return true;
  337.     else return false;
  338. }
  339. bool isChild(int child, int parent) {
  340.     if (child == getLeftChild(parent) || child == getRightChild(parent)) return true;
  341.     else return false;
  342. }
  343. int GetIndexOfSmallestOfChildrenAndGrandchildren(int i, int HeapSize, Node tab[]) {
  344.     int min;
  345.     int indexOfMin;
  346.     min = tab[getLeftChild(i)].value;
  347.     indexOfMin = getLeftChild(i);
  348.     if (getRightChild(i) < HeapSize) {
  349.         if (min > tab[getRightChild(i)].value) {
  350.             min = tab[getRightChild(i)].value;
  351.             indexOfMin = getRightChild(i);
  352.         }
  353.  
  354.         if (getGrandchild1(i) < HeapSize) {
  355.             if (min > tab[getGrandchild1(i)].value) {
  356.                 min = tab[getGrandchild1(i)].value;
  357.                 indexOfMin = getGrandchild1(i);
  358.             }
  359.             if (getGrandchild2(i) < HeapSize) {
  360.                 if (min > tab[getGrandchild2(i)].value) {
  361.                     min = tab[getGrandchild2(i)].value;
  362.                     indexOfMin = getGrandchild2(i);
  363.                 }
  364.                 if (getGrandchild3(i) < HeapSize) {
  365.                     if (min > tab[getGrandchild3(i)].value) {
  366.                         min = tab[getGrandchild3(i)].value;
  367.                         indexOfMin = getGrandchild3(i);
  368.                     }
  369.                     if (getGrandchild4(i) < HeapSize) {
  370.                         if (min > tab[getGrandchild4(i)].value) {
  371.                             min = tab[getGrandchild4(i)].value;
  372.                             indexOfMin = getGrandchild4(i);
  373.                         }
  374.                     }
  375.                 }
  376.             }
  377.         }
  378.     }
  379.     return indexOfMin;
  380. }
  381. int GetIndexOfBiggestOfChildrenAndGrandchildren(int i, int HeapSize, Node tab[])
  382. {
  383.     int max = 0;
  384.     int indexOfMax;
  385.  
  386.     if (getLeftChild(i) < HeapSize) {
  387.         max = tab[getLeftChild(i)].value;
  388.         indexOfMax = getLeftChild(i);
  389.     }
  390.     if (getRightChild(i) < HeapSize) {
  391.         if (max < tab[getRightChild(i)].value) {
  392.             max = tab[getRightChild(i)].value;
  393.             indexOfMax = getRightChild(i);
  394.         }
  395.     }
  396.     if (getGrandchild1(i) < HeapSize) {
  397.         if (max < tab[getGrandchild1(i)].value) {
  398.             max = tab[getGrandchild1(i)].value;
  399.             indexOfMax = getGrandchild1(i);
  400.         }
  401.     }
  402.     if (getGrandchild2(i) < HeapSize) {
  403.         if (max < tab[getGrandchild2(i)].value) {
  404.             max = tab[getGrandchild2(i)].value;
  405.             indexOfMax = getGrandchild2(i);
  406.         }
  407.     }
  408.     if (getGrandchild3(i) < HeapSize) {
  409.         if (max < tab[getGrandchild3(i)].value) {
  410.             max = tab[getGrandchild3(i)].value;
  411.             indexOfMax = getGrandchild3(i);
  412.         }
  413.     }
  414.     if (getGrandchild4(i) < HeapSize) {
  415.         if (max < tab[getGrandchild4(i)].value) {
  416.             max = tab[getGrandchild4(i)].value;
  417.             indexOfMax = getGrandchild4(i);
  418.         }
  419.     }
  420.     return indexOfMax;
  421. }
  422.  
  423.  
  424. #pragma endregion
  425. #pragma endregion
RAW Paste Data
Top