#include<stdio.h>
#include<stdlib.h>
#define min(a,b) ((a<b)?a:b)
typedef struct
{
long int thread_id;
long int ptime;
}pqueue;
pqueue * create_structure(pqueue * ptr, long int n);
pqueue * minheap(pqueue * ptr, long int n);
pqueue * siftdown(pqueue * ptr,long int pos,long int minpos,long int n);
pqueue * extractmax(pqueue * ptr, long int a[],long int i);
int main()
{
long int n,m,i;
pqueue *ptr;
long int a[m];
for(i=0;i<m;i++)
ptr=create_structure(ptr,n);
if(m>n)
{
for(i=0;i<n;i++)
ptr[i].ptime=a[i];
for(i=0;i<n;i++)
ptr=minheap(ptr,n);
{
printf("%ld %ld\n",ptr
[0].
thread_id,ptr
[0].
ptime); ptr= extractmax(ptr,a,i);
ptr = siftdown(ptr,0,0,n);
}
}
else
{
for(i=0;i<m;i++)
}
return 0;
}
pqueue * create_structure(pqueue * ptr, long int n)
{
ptr
= (pqueue
*)malloc(n
*sizeof(pqueue
)); for(int i=0;i<n;i++)
ptr[i].thread_id=i;
return ptr;
}
pqueue * minheap(pqueue * ptr, long int n)
{
long int i;
for(i=(n/2)-1 ;i>=0;i--)
{
ptr=siftdown(ptr,i,i,n);
}
return ptr;
}
pqueue * siftdown(pqueue * ptr,long int pos,long int minpos,long int n)
{
int left,right;
pqueue temp;
left= (2*pos) +1;
right=(2*pos) +2;
if(left> n && right> n)
return ptr;
if(left<n && ptr[left].ptime < ptr[pos].ptime)
minpos=left;
if(right<n && ptr[right].ptime < ptr[minpos].ptime)
minpos=right;
if(pos!=minpos)
{
if((left<n && right< n) && (ptr[left].ptime==ptr[right].ptime))
{
if(ptr[left].thread_id < ptr[right].thread_id)
minpos=left;
else
minpos=right;
}
temp=ptr[pos];
ptr[pos]=ptr[minpos];
ptr[minpos]=temp;
ptr = siftdown(ptr,minpos,minpos,n);
}
else if(minpos==pos)
{
pqueue temp;
if(left<n && right<n)
{
if(ptr[left].ptime==ptr[right].ptime && ptr[pos].ptime==ptr[left].ptime)
{
long int minid;
if(ptr[left].thread_id<ptr[right].thread_id)
minid=left;
else
minid=right;
if(ptr[pos].thread_id > ptr[minid].thread_id)
{
temp=ptr[pos];
ptr[pos]=ptr[minid];
ptr[minid]=temp;
ptr = siftdown(ptr,minid,minid,n);
}
}
}
if(left < n && right >=n)
{
if(ptr[left].thread_id < ptr[pos].thread_id)
{
minpos=left;
temp=ptr[pos];
ptr[pos]=ptr[minpos];
ptr[minpos]=temp;
ptr = siftdown(ptr,minpos,minpos,n);
}
}
if(right <n && left >=n)
{
if(ptr[right].thread_id < ptr[pos].thread_id)
{
minpos=right;
temp=ptr[pos];
ptr[pos]=ptr[minpos];
ptr[minpos]=temp;
ptr = siftdown(ptr,minpos,minpos,n);
}
}
}
return ptr;
}
pqueue * extractmax(pqueue * ptr, long int a[],long int i)
{
ptr[0].ptime+=a[i];
return ptr;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8c3RkbGliLmg+CiNkZWZpbmUgbWluKGEsYikgKChhPGIpP2E6YikKdHlwZWRlZiBzdHJ1Y3QKewogICAgICAgICAgbG9uZyBpbnQgdGhyZWFkX2lkOwogICAgICAgICAgbG9uZyBpbnQgcHRpbWU7Cn1wcXVldWU7CnBxdWV1ZSAqIGNyZWF0ZV9zdHJ1Y3R1cmUocHF1ZXVlICogcHRyLCAgbG9uZyBpbnQgbik7CnBxdWV1ZSAqIG1pbmhlYXAocHF1ZXVlICogcHRyLCBsb25nIGludCBuKTsKcHF1ZXVlICogc2lmdGRvd24ocHF1ZXVlICogcHRyLGxvbmcgaW50IHBvcyxsb25nIGludCBtaW5wb3MsbG9uZyBpbnQgbik7CnBxdWV1ZSAqIGV4dHJhY3RtYXgocHF1ZXVlICogcHRyLCBsb25nIGludCBhW10sbG9uZyBpbnQgaSk7CmludCBtYWluKCkKewogICAgICAgICBsb25nIGludCBuLG0saTsKICAgICAgICAgcHF1ZXVlICpwdHI7CiAgICAgICAgIHNjYW5mKCIlbGQgJWxkIiwmbiwmbSk7CiAgICAgICAgIGxvbmcgaW50IGFbbV07CiAgICAgICAgIGZvcihpPTA7aTxtO2krKykKICAgICAgICAgc2NhbmYoIiVsZCIsYStpKTsKICAgICAgICAgcHRyPWNyZWF0ZV9zdHJ1Y3R1cmUocHRyLG4pOwogICAgICAgICBpZihtPm4pCiAgICAgICAgIHsKICAgICAgICAgZm9yKGk9MDtpPG47aSsrKQogICAgICAgICBwdHJbaV0ucHRpbWU9YVtpXTsKICAgICAgICAgZm9yKGk9MDtpPG47aSsrKQogICAgICAgIHByaW50ZigiJWxkICVkXG4iLGksMCk7CiAgICAgICAgIHB0cj1taW5oZWFwKHB0cixuKTsKICAgICAgICAKICAgICAgICAgewogICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgICAgICBwcmludGYoIiVsZCAlbGRcbiIscHRyWzBdLnRocmVhZF9pZCxwdHJbMF0ucHRpbWUpOwogICAgICAgICAgICAgICAgICAgcHRyPSBleHRyYWN0bWF4KHB0cixhLGkpOwogICAgICAgICAgICAgICAgICAgcHRyID0gc2lmdGRvd24ocHRyLDAsMCxuKTsKICAgICAgICAgfQogICAgICAgICB9CiAgICAgICAgIGVsc2UKICAgICAgICAgewogICAgICAgICAgICAgZm9yKGk9MDtpPG07aSsrKQogICAgICAgICAgICAgcHJpbnRmKCIlZCAlZFxuIixpLDApOwogICAgICAgICB9CiAgICAgICAgICByZXR1cm4gMDsKfQpwcXVldWUgKiBjcmVhdGVfc3RydWN0dXJlKHBxdWV1ZSAqIHB0ciwgbG9uZyBpbnQgbikKewogICAgICAgICAgcHRyPSAocHF1ZXVlICopbWFsbG9jKG4qc2l6ZW9mKHBxdWV1ZSkpOwogICAgICAgICAgZm9yKGludCBpPTA7aTxuO2krKykKICAgICAgICAgIHB0cltpXS50aHJlYWRfaWQ9aTsKICAgICAgICAgIHJldHVybiBwdHI7Cn0KcHF1ZXVlICogbWluaGVhcChwcXVldWUgKiBwdHIsIGxvbmcgaW50IG4pCnsKICAgICAgICAgIGxvbmcgaW50IGk7CiAgICAgICAgICBmb3IoaT0obi8yKS0xIDtpPj0wO2ktLSkKICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgIHB0cj1zaWZ0ZG93bihwdHIsaSxpLG4pOwogICAgICAgICAgfQogICAgICAgICAgcmV0dXJuIHB0cjsKfQoKcHF1ZXVlICogc2lmdGRvd24ocHF1ZXVlICogcHRyLGxvbmcgaW50IHBvcyxsb25nIGludCBtaW5wb3MsbG9uZyBpbnQgbikKewogICAgICAgIAogICAgICAgICAgaW50IGxlZnQscmlnaHQ7CiAgICAgICAgICBwcXVldWUgdGVtcDsKICAgICAgICAgIGxlZnQ9ICgyKnBvcykgKzE7CiAgICAgICAgICByaWdodD0oMipwb3MpICsyOwogICAgICAgICAgaWYobGVmdD4gbiAmJiByaWdodD4gbikKICAgICAgICAgIHJldHVybiBwdHI7CiAgICAgICAgICBpZihsZWZ0PG4gJiYgcHRyW2xlZnRdLnB0aW1lIDwgcHRyW3Bvc10ucHRpbWUpCiAgICAgICAgICAgICAgICAgbWlucG9zPWxlZnQ7CiAgICAgICAgICBpZihyaWdodDxuICYmIHB0cltyaWdodF0ucHRpbWUgPCBwdHJbbWlucG9zXS5wdGltZSkKICAgICAgICAgICAgICAgICBtaW5wb3M9cmlnaHQ7CiAgICAgICAgICAgaWYocG9zIT1taW5wb3MpCiAgICAgICAgICB7CiAgICAgICAgIAogICAgICAgICAgaWYoKGxlZnQ8biAmJiByaWdodDwgbikgJiYgKHB0cltsZWZ0XS5wdGltZT09cHRyW3JpZ2h0XS5wdGltZSkpCiAgICAgICAgICB7CiAgICAgICAgICAgICAgaWYocHRyW2xlZnRdLnRocmVhZF9pZCA8IHB0cltyaWdodF0udGhyZWFkX2lkKQogICAgICAgICAgICAgIG1pbnBvcz1sZWZ0OwogICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICBtaW5wb3M9cmlnaHQ7CiAgICAgICAgICB9CiAgICAgICAgICAKICAgICAgICAgIHRlbXA9cHRyW3Bvc107CiAgICAgICAgICBwdHJbcG9zXT1wdHJbbWlucG9zXTsKICAgICAgICAgIHB0clttaW5wb3NdPXRlbXA7CiAgICAgICAgICBwdHIgPSBzaWZ0ZG93bihwdHIsbWlucG9zLG1pbnBvcyxuKTsKICAgICAgICAKICAgICAgICAgIH0KICAgICAgICAgIAogICAgICAgICAgZWxzZSBpZihtaW5wb3M9PXBvcykKICAgICAgICAgIHsKICAgICAgICAgCiAgICAgICAgICAgICAgcHF1ZXVlIHRlbXA7CiAgICAgICAgICAgICAgaWYobGVmdDxuICYmIHJpZ2h0PG4pCiAgICAgICAgICAgICAgewogICAgICAgICAgICAgIGlmKHB0cltsZWZ0XS5wdGltZT09cHRyW3JpZ2h0XS5wdGltZSAmJiBwdHJbcG9zXS5wdGltZT09cHRyW2xlZnRdLnB0aW1lKQogICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgbG9uZyBpbnQgbWluaWQ7CiAgICAgICAgICAgICAgICAgIGlmKHB0cltsZWZ0XS50aHJlYWRfaWQ8cHRyW3JpZ2h0XS50aHJlYWRfaWQpCiAgICAgICAgICAgICAgICAgIG1pbmlkPWxlZnQ7CiAgICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgICAgbWluaWQ9cmlnaHQ7CiAgICAgICAgICAgICAgICAgIGlmKHB0cltwb3NdLnRocmVhZF9pZCA+IHB0clttaW5pZF0udGhyZWFkX2lkKQogICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICB0ZW1wPXB0cltwb3NdOwogICAgICAgICAgICAgICAgICAgICAgcHRyW3Bvc109cHRyW21pbmlkXTsKICAgICAgICAgICAgICAgICAgICAgIHB0clttaW5pZF09dGVtcDsKICAgICAgICAgICAgICAgICAgICAgIHB0ciA9IHNpZnRkb3duKHB0cixtaW5pZCxtaW5pZCxuKTsKICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgICAKICAgICAgICAgICAgICAgICAgCiAgICAgICAgICAgICAgfQogICAgICAgICAgICAgIAogICAgICAgICAgICAgIH0KICAgICAgICAgICAgICBpZihsZWZ0IDwgbiAmJiByaWdodCA+PW4pCiAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICBpZihwdHJbbGVmdF0udGhyZWFkX2lkIDwgcHRyW3Bvc10udGhyZWFkX2lkKQogICAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgICBtaW5wb3M9bGVmdDsKICAgICAgICAgICAgICAgICAgICAgIHRlbXA9cHRyW3Bvc107CiAgICAgICAgICAgICAgICAgICAgICBwdHJbcG9zXT1wdHJbbWlucG9zXTsKICAgICAgICAgICAgICAgICAgICAgIHB0clttaW5wb3NdPXRlbXA7CiAgICAgICAgICAgICAgICAgICAgICBwdHIgPSBzaWZ0ZG93bihwdHIsbWlucG9zLG1pbnBvcyxuKTsKICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgIH0KICAgICAgICAgICAgICBpZihyaWdodCA8biAmJiBsZWZ0ID49bikKICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgIAogICAgICAgICAgICAgICAgICBpZihwdHJbcmlnaHRdLnRocmVhZF9pZCA8IHB0cltwb3NdLnRocmVhZF9pZCkKICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgbWlucG9zPXJpZ2h0OwogICAgICAgICAgICAgICAgICAgICAgdGVtcD1wdHJbcG9zXTsKICAgICAgICAgICAgICAgICAgICAgIHB0cltwb3NdPXB0clttaW5wb3NdOwogICAgICAgICAgICAgICAgICAgICAgcHRyW21pbnBvc109dGVtcDsKICAgICAgICAgICAgICAgICAgICAgIHB0ciA9IHNpZnRkb3duKHB0cixtaW5wb3MsbWlucG9zLG4pOwogICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgfQogICAgICAgICAgICAgIAogICAgICAgICAgfQogICAgICAgICAKICAgICAgICAgIAogICAgICAgICAgcmV0dXJuIHB0cjsKfQogcHF1ZXVlICogZXh0cmFjdG1heChwcXVldWUgKiBwdHIsIGxvbmcgaW50IGFbXSxsb25nIGludCBpKQogewoKICAgICAgICBwdHJbMF0ucHRpbWUrPWFbaV07CiAgICAgICAgcmV0dXJuIHB0cjsKIH0=