fork download
copy 
  1. #include <iostream>
  2. #include <climits>
  3. using namespace std;
  4.  
  5. struct Node{
  6.     long long int *data;
  7.     int eq_index;
  8. };
  9.  
  10. int GetLeftChild(int &parent){
  11.     return 2*parent+1;
  12. }
  13.  
  14. int GetRightChild(int &parent){
  15.     return 2*parent +2;
  16. }
  17.  
  18. int GetParent(int &child){
  19.     if (child % 2 == 0)
  20.         return (child /2 ) -1;
  21.     else
  22.         return child/2;
  23. }
  24.  
  25. void DoNode(int index, long long int *data, Node* Max, Node *Min){
  26.     Max[index].data=data;
  27.     Min[index].data=data;
  28.     Max[index].eq_index=index;
  29.     Min[index].eq_index=index;
  30. }
  31.  
  32. void RepUpMax(Node *MAX, Node *MIN, int in){
  33.     int P=GetParent(in);
  34.  
  35.     if(P>=0 && (*MAX[P].data<*MAX[in].data || (*MAX[P].data==*MAX[in].data && MAX[P].data>MAX[in].data))){
  36.         swap(MIN[MAX[P].eq_index].eq_index,MIN[MAX[in].eq_index].eq_index);
  37.                 swap(MAX[P].data,MAX[in].data);
  38.                 swap(MAX[P].eq_index,MAX[in].eq_index);
  39.         RepUpMax(MAX,MIN,P);
  40.     }
  41. }
  42.  
  43. void RepUpMin(Node *MAX, Node *MIN, int in){
  44.     int P=GetParent(in);
  45.     if(*MIN[in].data!=1){
  46.         if(P>=0 && (*MIN[P].data>*MIN[in].data || (*MIN[P].data==*MIN[in].data && MIN[P].data>MIN[in].data))){
  47.             swap(MAX[MIN[P].eq_index].eq_index,MAX[MIN[in].eq_index].eq_index);
  48.             swap(MIN[P].data,MIN[in].data);
  49.             swap(MIN[P].eq_index,MIN[in].eq_index);
  50.             RepUpMin(MAX,MIN,P);
  51.         }
  52.     }
  53.  
  54. }
  55.  
  56. Node* RepDownMax(Node *MAX, Node *MIN, int in, int size){
  57.     int B=in;
  58.     int L=GetLeftChild(in);
  59.     int R=GetRightChild(in);
  60.     if(L<size && (*MAX[B].data<*MAX[L].data || (*MAX[B].data==*MAX[L].data && MAX[B].data>MAX[L].data)))
  61.         B=L;
  62.     if(R<size && (*MAX[B].data<*MAX[R].data || (*MAX[B].data==*MAX[R].data && MAX[B].data>MAX[R].data)))
  63.         B=R;
  64.     if(B!=in){
  65.         swap(MIN[MAX[B].eq_index].eq_index,MIN[MAX[in].eq_index].eq_index);
  66.         swap(MAX[B].data,MAX[in].data);
  67.         swap(MAX[B].eq_index,MAX[in].eq_index);
  68.         return RepDownMax(MAX,MIN,B,size);
  69.     }
  70.     return MAX;
  71. }
  72.  
  73. Node* RepDownMin(Node *MAX, Node *MIN, int in, int size){
  74.     int S=in;
  75.     int L=GetLeftChild(in);
  76.     int R=GetRightChild(in);
  77.     if(L<size && (*MIN[S].data>*MIN[L].data || (*MIN[S].data==*MIN[L].data && MIN[S].data>MIN[L].data)))
  78.             S=L;
  79.         if(R<size && (*MIN[S].data>*MIN[R].data || (*MIN[S].data==*MIN[R].data && MIN[S].data>MIN[R].data)))
  80.             S=R;
  81.         if(S!=in){
  82.             swap(MAX[MIN[S].eq_index].eq_index,MAX[MIN[in].eq_index].eq_index);
  83.             swap(MIN[S].data,MIN[in].data);
  84.             swap(MIN[S].eq_index,MIN[in].eq_index);
  85.             return RepDownMax(MAX,MIN,S,size);
  86.         }
  87.  
  88.     return MIN;
  89. }
  90.  
  91. void RemoveMax(Node*MAX, Node*MIN, int &size, int index){
  92.     swap(MIN[MAX[index].eq_index].eq_index,MIN[MAX[size-1].eq_index].eq_index);
  93.     swap(MAX[index],MAX[size-1]);
  94.     RepDownMax(MAX,MIN,index,size-1);
  95.  
  96. }
  97.  
  98. void RemoveMin(Node*MAX,Node*MIN,int &size, int index){
  99.     swap(MAX[MIN[index].eq_index].eq_index,MAX[MIN[size-1].eq_index].eq_index);
  100.     swap(MIN[index],MIN[size-1]);
  101.     RepDownMin(MAX,MIN,index,size-1);
  102. }
  103.  
  104. void CollatzMin( Node *MAX, Node *MIN, int &size){
  105.     if(*MIN[0].data%2==0){
  106.        *MIN[0].data/=2;
  107.        if(*MIN[0].data==1){
  108.            RemoveMin(MAX,MIN,size,0);
  109.            RemoveMax(MAX,MIN,size,MIN[size-1].eq_index);
  110.            size--;
  111.        }
  112.        else
  113.        RepDownMax(MAX,MIN,MIN[0].eq_index,size);
  114.     }
  115.     else{
  116.         long long int tmp=3*(*MIN[0].data)+1;
  117.         if(tmp>UINT_MAX){
  118.             *MIN[0].data=0;
  119.             RemoveMin(MAX,MIN,size,0);
  120.             RemoveMax(MAX,MIN,size,MIN[size-1].eq_index);
  121.             size--;
  122.         }
  123.         else {
  124.             *MIN[0].data=tmp;
  125.             RepUpMax(MAX,MIN,MIN[0].eq_index);
  126.             RepDownMin(MAX,MIN,0,size);
  127.         }
  128.     }
  129. }
  130.  
  131. void CollatzMax( Node *MAX, Node *MIN, int &size){
  132.     if(*MAX[0].data%2!=0){
  133.         long long int tmp=3*(*MAX[0].data)+1;
  134.         if(tmp>UINT_MAX){
  135.             *MAX[0].data=0;
  136.             RemoveMax(MAX,MIN,size,0);
  137.             RemoveMin(MAX,MIN,size,MAX[size-1].eq_index);
  138.             size--;
  139.         }
  140.         else{
  141.             *MAX[0].data=tmp;
  142.             RepDownMin(MAX,MIN,MAX[0].eq_index,size);
  143.         }
  144.     }
  145.     else{
  146.         *MAX[0].data/=2;
  147.         if(*MAX[0].data==1){
  148.             RemoveMax(MAX,MIN,size,0);
  149.             RemoveMin(MAX,MIN,size,MAX[size-1].eq_index);
  150.             size--;
  151.         }
  152.  
  153.         else
  154.         {
  155.             RepUpMin(MAX,MIN,MAX[0].eq_index);
  156.             RepDownMax(MAX,MIN,0,size);
  157.         }
  158.  
  159.     }
  160.  
  161. }
  162.  
  163. int main() {
  164.     int ile,con=0,kom;
  165.     long long int tmp;
  166.     cin>>ile;
  167.  
  168.     long long int *tablica=new long long int [ile];
  169.     Node *MaxHeap=new Node [ile];
  170.     Node *MinHeap=new Node [ile];
  171.     for(int i=0; i<ile; i++){
  172.         cin>>tmp;
  173.         if(tmp>UINT_MAX)
  174.         tablica[i]=0;
  175.         else if(tmp==1)
  176.             tablica[i]=1;
  177.         else if(tmp!=1){
  178.             tablica[i]=tmp;
  179.             DoNode(con,tablica+i,MaxHeap,MinHeap);
  180.             RepUpMax(MaxHeap,MinHeap,con);
  181.             RepUpMin(MaxHeap,MinHeap,con);
  182.             con++;
  183.         }
  184.  
  185.     }
  186.  
  187.     cin>>kom;
  188.     int ikom;
  189.     char wg;
  190.     for(int i=0; i<kom; i++){
  191.         cin>>ikom>>wg;
  192.         for(int j=0; j<ikom; j++){
  193.             if(wg=='s')
  194.                 CollatzMin(MaxHeap,MinHeap,con);
  195.             else
  196.                 CollatzMax(MaxHeap,MinHeap,con);
  197.         }
  198.     }
  199.  
  200.     for(int i=0; i<ile; i++){
  201.         if(tablica[i]==0) cout<<"m ";
  202.         else
  203.         cout<<tablica[i]<<' ';
  204.     }
  205.     cout<<endl;
  206.     return 0;
  207. }
  208.  
Success #stdin #stdout 0s 4408KB
comments (?)
stdin
copy 
4
 1 3 3 2000000001
 2
 2 L
 1 S
stdout
copy 
1 5 3 m
https://ideone.com/VwHTsL
language:
C++14 (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!