Advertisement
Guest User

Untitled

a guest
Jul 28th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.47 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. struct tree
  7. {
  8.     int key;
  9.     tree *right, *left, *parent;
  10.     int countLeft, countRight;
  11.     tree()
  12.     {
  13.         countLeft = countRight = 0;
  14.         parent = right = left = NULL;
  15.     }
  16. };
  17.  
  18. tree* tStart = NULL, *tFin = NULL;
  19. bool flag = false;
  20. tree *v = NULL;
  21. int MAX = -2147483647;
  22.  
  23. bool addElem(tree* &t, int &n)
  24. {
  25.     if (t != NULL)
  26.     {
  27.         if (n < t->key)
  28.         {
  29.             t->countLeft++;
  30.             if (t->left)
  31.                 return addElem(t->left, n);
  32.             else
  33.             {
  34.                 t->left = new tree;
  35.                 t->left->key = n;
  36.                 t->left->parent = t;
  37.             }
  38.         }
  39.         else if (n > t->key)
  40.         {
  41.             t->countRight++;
  42.             if (t->right)
  43.                 return addElem(t->right, n);
  44.             else
  45.             {
  46.                 t->right = new tree;
  47.                 t->right->key = n;
  48.                 t->right->parent = t;
  49.             }
  50.         }
  51.         else return false;
  52.     }
  53.     else
  54.     {
  55.         t = new tree();
  56.         t->key = n;
  57.     }
  58.     return true;
  59. }
  60.  
  61. bool checkStruct(tree* tr1, tree* tr2)
  62. {
  63.     if (tr1==NULL && tr2==NULL)
  64.         return true;
  65.     else if ((tr1 == NULL && tr2 != NULL) || (tr1 != NULL && tr2 == NULL))
  66.         return false;
  67.     else return checkStruct(tr1->left, tr2->left)*checkStruct(tr1->right, tr2->right);
  68. }
  69.  
  70. void findV(tree *tr1, tree *tr2, tree* &v)
  71. {
  72.     if (tr1->countLeft != tr2->countLeft && tr1->countRight == tr2->countRight)
  73.     {
  74.         if (!checkStruct(tr1->right, tr2->right))
  75.             return;
  76.         if (tr1->left == NULL && tr2->left != NULL)
  77.         {
  78.             v = tr2->left;
  79.         }
  80.         else findV(tr1->left, tr2->left, v);
  81.     }
  82.     else if (tr1->countLeft == tr2->countLeft && tr1->countRight != tr2->countRight)
  83.     {
  84.         if (!checkStruct(tr1->left, tr2->left))
  85.             return;
  86.         if (tr1->right == NULL && tr2->right != NULL)
  87.         {
  88.             v = tr2->right;
  89.         }
  90.         else findV(tr1->right, tr2->right, v);
  91.     }
  92.     else if (checkStruct(tr2->left, tr1) || checkStruct(tr2->right, tr1))
  93.     {
  94.         v = tr2;
  95.     }
  96. }
  97.  
  98. bool leftDel(tree* v)
  99. {
  100.     while (v = v->parent)
  101.     {
  102.         if (v->parent)
  103.         {
  104.             if (v->parent->left == v)
  105.             {
  106.                 if (v->parent->right)
  107.                     MAX = v->parent->key;
  108.                 return true;
  109.             }
  110.         }
  111.         else return false;
  112.     }
  113.     return false;
  114. }
  115.  
  116. bool isLeft(tree* t)
  117. {
  118.     while (t = t->right)
  119.     {
  120.         if (t->left)
  121.             return true;
  122.     }
  123.     return false;
  124. }
  125.  
  126. int main()
  127. {
  128.     ifstream in("tst.in");
  129.     char str[10];
  130.     int k=0;
  131.     int col1=0, col2=0;
  132.     bool flag = false;
  133.     while (true)
  134.     {
  135.         in >> str;
  136.         if (!in)
  137.             break;
  138.         if (!strcmp(str, "*"))
  139.         {
  140.             flag = true;
  141.             continue;
  142.         }
  143.         k = atoi(str);
  144.         if (flag)
  145.         {
  146.             if (addElem(tFin, k))
  147.                 col2++;
  148.         }
  149.         else
  150.         {
  151.             if (addElem(tStart, k))
  152.                 col1++;
  153.         }
  154.     }
  155.     in.close();
  156.     ofstream out("tst.out");
  157.     if ((abs(col1 - col2) != 1) || (!(tStart&&tFin)))
  158.     {
  159.         out << "NO";
  160.         out.close();
  161.         return 0;
  162.     }
  163.     if (col1 > col2)
  164.     {
  165.         tree* tmp = tStart;
  166.         tStart = tFin;
  167.         tFin = tmp;
  168.     }
  169.     findV(tStart, tFin, v);
  170.     if (!v)
  171.     {
  172.         out << "NO";
  173.         out.close();
  174.         return 0;
  175.     }
  176.     else out << "YES\n";
  177.  
  178.     MAX = v->key;
  179.  
  180.     if (v == tFin)
  181.     {
  182.         MAX = v->key;
  183.     }
  184.     else if (v->parent->right == v)
  185.     {
  186.         if (v->right)
  187.         {
  188.             if (!isLeft(v))
  189.             {
  190.                 leftDel(v);
  191.             }
  192.         }
  193.         else leftDel(v);
  194.     }
  195.     else if (v->parent->left == v)
  196.     {
  197.         if (v->parent->right)
  198.         {
  199.             if (!isLeft(v))
  200.             {
  201.                 MAX = v->parent->key;
  202.             }
  203.         }
  204.         else if (isLeft(v))
  205.         {
  206.            
  207.         }
  208.         else
  209.         {
  210.             while (v = v->parent)
  211.             {
  212.                 MAX = v->key;
  213.                 if (v->right || !v->parent)
  214.                     break;
  215.                 if (v->parent->right == v)
  216.                 {
  217.                     if (v->right == NULL)
  218.                         leftDel(v);
  219.                     break;
  220.                 }
  221.             }
  222.         }
  223.     }
  224.  
  225.     out << MAX << endl;
  226.     out.close();
  227.     return 0;
  228. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement