Ledger Nano X - The secure hardware wallet
SHARE
TWEET

Untitled

a guest Feb 19th, 2020 73 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <fstream>
  3. #include <string>
  4. #define INPUT_FILE "input.txt"
  5. #define OUTPUT_FILE "output.txt"
  6.  
  7. using namespace std;
  8.  
  9. fstream infile, outfile;
  10.  
  11. template <class H>
  12. struct Nodo
  13. {
  14.     H val;
  15.     Nodo<H>* padre;
  16.     Nodo<H>* sinistro;
  17.     Nodo<H>* destro;
  18. };
  19.  
  20. template <class H>
  21. class BST
  22. {
  23.     private:
  24.         Nodo<H>* radice;
  25.     public:
  26.         BST() : radice(NULL) {}
  27.         void insert(H valore);
  28.         void trapianta(Nodo<H>* u, Nodo<H>* v);
  29.         Nodo<H>* find(H x);
  30.         void cancella(Nodo<H>* z);
  31.         Nodo<H>* minimo(Nodo<H>* x);
  32.         Nodo<H>* _succ(Nodo<H>* aux);
  33.         H succ(H valore);
  34. };
  35.  
  36. template <class H>
  37. void BST<H>::insert(H valore)
  38. {
  39.     Nodo<H>* nuovo = new Nodo<H>;
  40.     Nodo<H>* x = radice, *y = NULL;
  41.     nuovo -> val = valore;
  42.     nuovo -> sinistro = nuovo -> destro = NULL;
  43.     while (x!=NULL)
  44.     {
  45.         y = x;
  46.         if (valore < x->val)
  47.             x = x->sinistro;
  48.         else
  49.             x = x->destro;
  50.     }
  51.  
  52.     nuovo -> padre = y;
  53.     if (y==NULL)
  54.         radice = nuovo;
  55.     else if (valore < y->val)
  56.         y -> sinistro = nuovo;
  57.     else
  58.         y -> destro = nuovo;
  59. }
  60.  
  61. template <class H>
  62. void BST<H>::trapianta(Nodo<H>* u, Nodo<H>* v)
  63. {
  64.     if (u->padre==NULL)
  65.         radice = v;
  66.     else if (u==u->padre->sinistro)
  67.         u->padre->sinistro = v;
  68.     else
  69.         u-> padre -> destro = v;
  70.     if (v!=NULL)
  71.         v->padre = u->padre;
  72. }
  73.  
  74. template <class H>
  75. Nodo<H>* BST<H>::minimo(Nodo<H>* x)
  76. {
  77.     Nodo<H>* min = x;
  78.     while (min->sinistro != NULL)
  79.         min = min->sinistro;
  80.     return min;
  81. }
  82.  
  83. template <class H>
  84. void BST<H>::cancella(Nodo<H>* z)
  85. {
  86.     Nodo<H>* y;
  87.     if (z->sinistro == NULL)
  88.         trapianta(z, z->destro);
  89.     else if (z->destro == NULL)
  90.         trapianta(z, z->sinistro);
  91.     else
  92.     {
  93.         y = minimo(z->destro);
  94.         if (y->padre!=z)
  95.         {
  96.             trapianta(y, y->destro);
  97.             y->destro = z->destro;
  98.             y->destro->padre = y;
  99.         }
  100.         trapianta(z, y);
  101.         y->sinistro = z->sinistro;
  102.         y->sinistro->padre = y;
  103.     }
  104.     delete z;
  105. }
  106.  
  107. template <class H>
  108. Nodo<H>* BST<H>::find(H x)
  109. {
  110.     Nodo<H>* iter = radice;
  111.     while ((iter!=NULL)&&(x!=iter->val))
  112.     {
  113.         if (x<iter->val)
  114.             iter = iter->sinistro;
  115.         else
  116.             iter = iter -> destro;
  117.     }
  118.     return iter;
  119. }
  120.  
  121. template <class H>
  122. Nodo<H>* BST<H>::_succ(Nodo<H>* aux)
  123. {
  124.     if (aux==0)
  125.         return 0;
  126.     if (aux->destro)
  127.         return minimo(aux->destro);
  128. }
  129.  
  130. template <class H>
  131. H BST<H>::succ(H val)
  132. {
  133.     Nodo<H>* aux = _succ(find(val));
  134.     if (aux)
  135.         return aux->val;
  136.     else
  137.         return -1;
  138. }
  139.  
  140. int getDuePunti(string x)
  141. {
  142.     for (int i=0; i<x.length(); i++)
  143.         if (x[i]==':')
  144.             return i;
  145.     return 0;
  146. }
  147.  
  148. string getOp(string x)
  149. {
  150.     return x.substr(0, getDuePunti(x));
  151. }
  152.  
  153. string _getValore(string x)
  154. {
  155.     return x.substr(getDuePunti(x)+1, x.length());
  156. }
  157.  
  158. int main()
  159. {
  160.     infile.open(INPUT_FILE, fstream::in);
  161.     outfile.open(OUTPUT_FILE, fstream::out);
  162.     for (int k=0; k<100; k++)
  163.     {
  164.         string tipo;
  165.         int N, M;
  166.         infile >> tipo >> N >> M;
  167.         if (tipo=="int")
  168.         {
  169.             BST<int> tree;
  170.             for (int j=0; j<N; j++)
  171.             {
  172.                 string tmp, _valore, op;
  173.                 int x;
  174.                 infile >> tmp;
  175.                 op = getOp(tmp);
  176.                 _valore = _getValore(tmp);
  177.                 x = stoi(_valore);
  178.  
  179.                 if (op=="ins")
  180.                     tree.insert(x);
  181.                 else
  182.                 {
  183.                     Nodo<int>* elem = tree.find(x);
  184.                     tree.cancella(elem);
  185.                 }
  186.             }
  187.             for (int j=0; j<M; j++)
  188.             {
  189.                 int chiave;
  190.                 infile >> chiave;
  191.                 int successore = tree.succ(chiave);
  192.                 outfile << successore << " ";
  193.             }
  194.         }
  195.         else
  196.         {
  197.             BST<double> tree;
  198.             for (int j=0; j<N; j++)
  199.             {
  200.                 string tmp, _valore, op;
  201.                 double x;
  202.                 infile >> tmp;
  203.                 op = getOp(tmp);
  204.                 _valore = _getValore(tmp);
  205.                 x = stod(_valore);
  206.  
  207.                 if (op=="ins")
  208.                     tree.insert(x);
  209.                 else
  210.                 {
  211.                     Nodo<double>* elem = tree.find(x);
  212.                     tree.cancella(elem);
  213.                 }
  214.             }
  215.             for (int j=0; j<M; j++)
  216.             {
  217.                 int chiave;
  218.                 infile >> chiave;
  219.                 int successore = tree.succ(chiave);
  220.                 outfile << successore << " ";
  221.             }
  222.         }
  223.         outfile << endl;
  224.     }
  225.     cout << "end of program, exit" << endl;
  226.     infile.close();
  227.     outfile.close();
  228. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top