Cod sursa(job #1261515)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 12 noiembrie 2014 14:49:13
Problema Interclasari Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.36 kb
#include<stdio.h>
#define MAX 4000000
int hSize,heap[MAX];
inline int left(int x){
    return x*2+1;
}
inline int right(int x){
    return x*2+2;
}
inline int parent(int x){
    if(x)
        return (x-1)/2;
    else
        return -1;
}
void insert(int x){
    heap[hSize++]=x;
    int poz=hSize-1;
    while(parent(poz)!=-1&&heap[poz]<heap[parent(poz)]){
        int aux=heap[poz];
        heap[poz]=heap[parent(poz)];
        heap[parent(poz)]=aux;
        poz=parent(poz);
    }
}
void pop(){
    heap[0]=heap[hSize-1];
    int x=0,y=1;
    while(x!=y){
        y=x;
        if(left(y)<hSize&&heap[left(y)]<heap[x])
            x=left(y);
        if(right(y)<hSize&&heap[right(y)]<heap[x])
            x=right(y);
        int aux=heap[x];
        heap[x]=heap[y];
        heap[y]=aux;
    }
}
int main(){
    FILE *fin,*fout;
    fin=fopen("interclasari.in","r");
    fout=fopen("interclasari.out","w");
    int n,i;
    fscanf(fin,"%d",&n);
    for(i=0;i<n;i++){
        int k,j;
        fscanf(fin,"%d",&k);
        for(j=0;j<k;j++){
            int x;
            fscanf(fin,"%d",&x);
            insert(x);
        }
    }
    fprintf(fout,"%d\n",hSize);
    while(hSize){
        if(heap[0]==0)
            hSize++,hSize--;
        fprintf(fout,"%d ",heap[0]);
        pop();
        hSize--;
    }
    return 0;
}