fork download
copy 
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. struct node{
  4.     int val;
  5.     struct node *next;
  6.     struct node *prev;
  7.     struct tree *prev_tree;
  8. };
  9. struct tree{
  10.     int val;
  11.     struct tree *l;
  12.     struct tree *r;
  13.     struct tree *p;
  14.     struct node *next;
  15.     struct node *prev;
  16. };
  17. int cmp(struct tree* A, struct tree* B)//Function to cmp two arbitrary large numbers
  18. {   
  19.     struct node *tree1=NULL;
  20.     struct node *tree2=NULL;
  21.     int i=0;
  22.     tree1=(struct node *)malloc(sizeof(struct node)); 
  23.     tree1=A->next;
  24.     tree2=(struct node *)malloc(sizeof(struct node));
  25.     tree2=B->next;
  26.     if(tree1!=NULL&&tree2!=NULL)
  27.     {
  28.         while(tree1->next!=NULL)
  29.         {
  30.             tree1=tree1->next;
  31.         }
  32.         while(tree2->next!=NULL)
  33.         {
  34.             tree2=tree2->next;
  35.         }
  36.         while(tree1->prev!=NULL&&tree2->prev!=NULL)
  37.         {
  38.             tree1=tree1->prev;
  39.             tree2=tree2->prev;
  40.         }
  41.         if(tree1->prev==NULL&&tree2->prev!=NULL)
  42.         {
  43.             tree2=tree2->prev;
  44.         }
  45.         if(tree2->prev==NULL&&tree1->prev!=NULL)
  46.         {   
  47.             tree1=tree1->prev;
  48.         }
  49.         if(tree1->prev==NULL&&tree2->prev!=NULL)
  50.         {
  51.             return 0;
  52.         }
  53.         if(tree2->prev==NULL&&tree1->prev!=NULL)
  54.         {
  55.             return 1;
  56.         }
  57.         while(tree1!=NULL||tree2!=NULL)
  58.         {   
  59.             if(i==0)
  60.             {   
  61.                 if(A->val>B->val)
  62.                 {
  63.                     return 1;
  64.                 }
  65.                 if(B->val>A->val)
  66.                 {
  67.                     return 0;
  68.                 }
  69.                 tree1=A->next;
  70.                 tree2=B->next;
  71.                 i++;
  72.                 continue;
  73.             }
  74.             if(tree1->val>tree2->val)
  75.             {
  76.                 return 1;
  77.             }
  78.             if(tree2->val>tree1->val)
  79.             {
  80.                 return 0;
  81.             }
  82.             tree1=tree1->next;
  83.             tree2=tree2->next;
  84.         }
  85.  
  86.     }
  87.     else
  88.     {
  89.         if(A->val>B->val)
  90.         {
  91.             return 1;
  92.         }
  93.         if(B->val>A->val)
  94.         {
  95.             return 0;
  96.         }
  97.     }
  98.     return 2;
  99. }
  100. struct tree* p(struct tree *A, struct tree *B)//Gives the p of new node to be inserted
  101. {   
  102.     struct tree* n=NULL;
  103.     n=(struct tree *)malloc(sizeof(struct tree));
  104.     while(B!=NULL)
  105.     {
  106.         if(cmp(A,B)==1)
  107.         {   
  108.             n=B;
  109.             B=B->r;
  110.             continue;
  111.         }
  112.         if(cmp(A,B)==0)
  113.         {
  114.             n=B;
  115.             B=B->l;
  116.             continue;
  117.         }
  118.     }   
  119.     return n;
  120. }
  121. struct tree* n_tree(int val)
  122. {
  123.     struct tree *n;
  124.     n=(struct tree *)malloc(sizeof(struct tree));
  125.     n->val=val;
  126.     n->l=NULL;
  127.     n->r=NULL;
  128.     n->prev=NULL;
  129.     n->next=NULL;
  130.     n->p=NULL;
  131.     return n;
  132. }
  133. void preorder(struct tree* node) 
  134. { 
  135.     if(node == NULL) 
  136.     {
  137.         return; 
  138.     }
  139.     printf("%d", node->val);   
  140.     preorder(node->l); 
  141.     preorder(node->r); 
  142. } 
  143. struct node* n_node(int val, struct node *a)
  144. {
  145.     struct node *n;
  146.     n=(struct node *)malloc(sizeof(struct node));
  147.     n->val=val;
  148.     n->prev=a;
  149.     if(a!=NULL)
  150.     {
  151.         a->next=n;
  152.     }
  153.     n->next=NULL;
  154.     n->prev_tree=NULL;
  155.     return n;
  156. }
  157. struct node* head(int val)
  158. {
  159.     struct node *n;
  160.     n=(struct node *)malloc(sizeof(struct node));
  161.     n->next=NULL;
  162.     n->prev=NULL;
  163.     n->prev_tree=NULL;
  164.     n->val=val;
  165.     return n;
  166. }
  167. void pos(struct tree *t, struct tree *root)
  168. {
  169.     while(root!=NULL)
  170.     {
  171.         if(cmp(t,root)==2)
  172.         {
  173.             printf("\n");
  174.             break;
  175.         }
  176.         if(cmp(t,root)==1)
  177.         {
  178.             root=root->r;
  179.             printf("1");
  180.             continue;       
  181.         }
  182.         root=root->l;
  183.         printf("0");
  184.     }
  185.     return;
  186. }
  187. int main()
  188. {
  189.     int c_1,c_2,c_3,f1=0,f2=0,f3=0,f4=0,i=0,j=0,k=0,m=1;
  190.     struct tree *root=NULL;
  191.     struct node *tree1=NULL;
  192.     struct tree *tree2=NULL;
  193.     struct node *temp_1=NULL;
  194.     struct tree *temp_2=NULL;
  195.     struct tree *p_node=NULL;
  196.     p_node=(struct tree *)malloc(sizeof(struct tree));
  197.     temp_2=(struct tree *)malloc(sizeof(struct tree));
  198.     temp_1=(struct node *)malloc(sizeof(struct node));
  199.     tree1=(struct node *)malloc(sizeof(struct node));
  200.     tree2=(struct tree *)malloc(sizeof(struct tree));   
  201.     root=(struct tree *)malloc(sizeof(struct tree));
  202.     root->val=-2;
  203.     root->p=NULL;
  204.     root->l=NULL;
  205.     root->r=NULL;
  206.     root->prev=NULL;
  207.     root->next=NULL;
  208.     while((c_1=fgetc(stdin))!=EOF)
  209.     {
  210.         if(c_1=='N')
  211.         {
  212.             c_2=c_1;
  213.             continue;   
  214.         }
  215.         else if(c_1=='S')
  216.         {       
  217.             c_2=c_1;
  218.             continue;
  219.         }
  220.         else if(c_1=='P')
  221.         {
  222.             c_2=c_1;
  223.             continue;
  224.         }
  225.         else if((c_1==' ')&&(c_2=='N')&&(f1==0))
  226.         {   
  227.             f1=1;
  228.             continue;
  229.         }
  230.         else if((c_1==' ')&&(c_2=='S')&&(f2==0))
  231.         {   
  232.             f2=1;
  233.             continue;
  234.         }
  235.         else if((c_1==' ')&&(c_2=='P')&&(f3==0))
  236.         {
  237.             f3=1;
  238.             continue;
  239.         }
  240.         else if(f1==1)
  241.         {
  242.             if(i==0)
  243.             {   
  244.                 root->val=c_1-'0';
  245.                 tree2=root;               
  246.                 i++;
  247.                 printf("%d",root->val);
  248.                 continue;
  249.             }
  250.             if(c_1!=' '&&c_1!='\n')
  251.             {
  252.                 if(i==1)
  253.                 {
  254.                     tree1=n_node(c_1-'0',NULL);
  255.                     tree1->prev_tree=root;
  256.                     root->next=tree1;
  257.                     temp_1=tree1;
  258.                     printf("%d",tree1->val);
  259.                     i=i+3;
  260.                     tree2=root;
  261.                     continue;
  262.                 }
  263.                 if(i==2)
  264.                 {   
  265.                     tree2=n_tree(c_1-'0');
  266.                     printf("%d",tree2->val);
  267.                     i++;
  268.                     continue;
  269.                 }
  270.                 if(i==3)
  271.                 {
  272.                     tree1=n_node(c_1-'0',NULL);
  273.                     tree1->prev_tree=tree2;
  274.                     tree2->next=tree1;
  275.                     temp_1=tree1;
  276.                     printf("%d",tree1->val);
  277.                     i++;
  278.                     continue;
  279.                 }
  280.                 tree1=n_node(c_1-'0',tree1);
  281.                 printf("%d",tree1->val); 
  282.                 continue;
  283.             }
  284.             if(c_1==' ')
  285.             {
  286.                 if(k==0)
  287.                 {   printf(" ");
  288.                     i=2;
  289.                     k++;
  290.                     continue;
  291.                 }
  292.                 p_node=p(tree2,root);
  293.                 printf(" %d ",p_node->val);
  294.                 tree2->p=p_node;
  295.                 if(cmp(tree2,p_node)==1)
  296.                 {
  297.                     p_node->r=tree2;
  298.                 }
  299.                 if(cmp(tree2,p_node)==0)
  300.                 {
  301.                     p_node->l=tree2;
  302.                 }
  303.                 i=2;
  304.                 continue;
  305.  
  306.             }
  307.             if(c_1=='\n')
  308.             {   
  309.                 p_node=p(tree2,root);
  310.                 printf(" %d ",p_node->val);                
  311.                 tree2->p=p_node;
  312.                 if(cmp(tree2,p_node)==1)
  313.                 {
  314.                     p_node->r=tree2;
  315.                 }
  316.                 if(cmp(tree2,p_node)==0)
  317.                 {
  318.                     p_node->l=tree2;
  319.                 }
  320.                 f1=0;
  321.                 continue;
  322.             }       
  323.         }
  324.         else if(f2==1)
  325.         {   
  326.             if(j==0)
  327.             {   
  328.                 temp_2=n_tree(c_1-'0');
  329.                 printf("%d",temp_2->val);
  330.                 j++;
  331.                 continue;
  332.             }
  333.             if(c_1=='\n')
  334.             {                       
  335.                 pos(temp_2, root);
  336.                 break;
  337.             }
  338.             if(m==1)
  339.             {
  340.                 tree1=n_node(c_1-'0',NULL);
  341.                 tree1->prev_tree=temp_2;
  342.                 temp_2->next=tree1;
  343.                 printf("%d",tree1->val);
  344.                 m++;
  345.                 continue;
  346.             }
  347.             tree1=n_node(c_1-'0',tree1);
  348.             printf("%d",tree1->val);            
  349.         }               
  350.     }
  351.     return 0;
  352. }
Success #stdin #stdout 0s 9424KB
comments (?)
stdin
copy 
N 12 15 14 16 18 13
S 16
S 15
stdout
copy 
12 15 1 14 1 16 1 18 1 13 1 1611
https://ideone.com/QAPUZ9
language:
C (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!