fork download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #define min(a,b) ((a<b)?a:b)
  4. typedef struct
  5. {
  6.           long int thread_id;
  7.           long int ptime;
  8. }pqueue;
  9. pqueue * create_structure(pqueue * ptr,  long int n);
  10. pqueue * minheap(pqueue * ptr, long int n);
  11. pqueue * siftdown(pqueue * ptr,long int pos,long int minpos,long int n);
  12. pqueue * extractmax(pqueue * ptr, long int a[],long int i);
  13. int main()
  14. {
  15.          long int n,m,i;
  16.          pqueue *ptr;
  17.          scanf("%ld %ld",&n,&m);
  18.          long int a[m];
  19.          for(i=0;i<m;i++)
  20.          scanf("%ld",a+i);
  21.          ptr=create_structure(ptr,n);
  22.          if(m>n)
  23.          {
  24.          for(i=0;i<n;i++)
  25.          ptr[i].ptime=a[i];
  26.          for(i=0;i<n;i++)
  27.         printf("%ld %d\n",i,0);
  28.          ptr=minheap(ptr,n);
  29.  
  30.          {
  31.  
  32.                    printf("%ld %ld\n",ptr[0].thread_id,ptr[0].ptime);
  33.                    ptr= extractmax(ptr,a,i);
  34.                    ptr = siftdown(ptr,0,0,n);
  35.          }
  36.          }
  37.          else
  38.          {
  39.              for(i=0;i<m;i++)
  40.              printf("%d %d\n",i,0);
  41.          }
  42.           return 0;
  43. }
  44. pqueue * create_structure(pqueue * ptr, long int n)
  45. {
  46.           ptr= (pqueue *)malloc(n*sizeof(pqueue));
  47.           for(int i=0;i<n;i++)
  48.           ptr[i].thread_id=i;
  49.           return ptr;
  50. }
  51. pqueue * minheap(pqueue * ptr, long int n)
  52. {
  53.           long int i;
  54.           for(i=(n/2)-1 ;i>=0;i--)
  55.           {
  56.  
  57.                    ptr=siftdown(ptr,i,i,n);
  58.           }
  59.           return ptr;
  60. }
  61.  
  62. pqueue * siftdown(pqueue * ptr,long int pos,long int minpos,long int n)
  63. {
  64.  
  65.           int left,right;
  66.           pqueue temp;
  67.           left= (2*pos) +1;
  68.           right=(2*pos) +2;
  69.           if(left> n && right> n)
  70.           return ptr;
  71.           if(left<n && ptr[left].ptime < ptr[pos].ptime)
  72.                  minpos=left;
  73.           if(right<n && ptr[right].ptime < ptr[minpos].ptime)
  74.                  minpos=right;
  75.            if(pos!=minpos)
  76.           {
  77.  
  78.           if((left<n && right< n) && (ptr[left].ptime==ptr[right].ptime))
  79.           {
  80.               if(ptr[left].thread_id < ptr[right].thread_id)
  81.               minpos=left;
  82.               else
  83.               minpos=right;
  84.           }
  85.  
  86.           temp=ptr[pos];
  87.           ptr[pos]=ptr[minpos];
  88.           ptr[minpos]=temp;
  89.           ptr = siftdown(ptr,minpos,minpos,n);
  90.  
  91.           }
  92.  
  93.           else if(minpos==pos)
  94.           {
  95.  
  96.               pqueue temp;
  97.               if(left<n && right<n)
  98.               {
  99.               if(ptr[left].ptime==ptr[right].ptime && ptr[pos].ptime==ptr[left].ptime)
  100.               {
  101.                   long int minid;
  102.                   if(ptr[left].thread_id<ptr[right].thread_id)
  103.                   minid=left;
  104.                   else
  105.                   minid=right;
  106.                   if(ptr[pos].thread_id > ptr[minid].thread_id)
  107.                   {
  108.                       temp=ptr[pos];
  109.                       ptr[pos]=ptr[minid];
  110.                       ptr[minid]=temp;
  111.                       ptr = siftdown(ptr,minid,minid,n);
  112.                   }
  113.  
  114.  
  115.               }
  116.  
  117.               }
  118.               if(left < n && right >=n)
  119.               {
  120.  
  121.                   if(ptr[left].thread_id < ptr[pos].thread_id)
  122.                   {
  123.                       minpos=left;
  124.                       temp=ptr[pos];
  125.                       ptr[pos]=ptr[minpos];
  126.                       ptr[minpos]=temp;
  127.                       ptr = siftdown(ptr,minpos,minpos,n);
  128.                   }
  129.               }
  130.               if(right <n && left >=n)
  131.               {
  132.  
  133.                   if(ptr[right].thread_id < ptr[pos].thread_id)
  134.                   {
  135.                       minpos=right;
  136.                       temp=ptr[pos];
  137.                       ptr[pos]=ptr[minpos];
  138.                       ptr[minpos]=temp;
  139.                       ptr = siftdown(ptr,minpos,minpos,n);
  140.                   }
  141.               }
  142.  
  143.           }
  144.  
  145.  
  146.           return ptr;
  147. }
  148.  pqueue * extractmax(pqueue * ptr, long int a[],long int i)
  149.  {
  150.  
  151.         ptr[0].ptime+=a[i];
  152.         return ptr;
  153.  }
Runtime error #stdin #stdout 0s 4472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/y2OuDB
language:
C (gcc 8.3)
created:
4 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!