Cod sursa(job #1798583)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 5 noiembrie 2016 12:12:49
Problema Interclasari Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <stdio.h>
#include <stdlib.h>

#define BUF_SIZE 16384
char buf[BUF_SIZE];
int pbuf=BUF_SIZE;
FILE*fi,*fo;
inline char nextch(){
    if(pbuf==BUF_SIZE){
        fread(buf, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buf[pbuf++];
}
inline long long nextnum(){
    long long a=0;
    char c=nextch();
    while((c<'0' || c>'9') && c!='-')
        c=nextch();
    int semn=1;
    if(c=='-'){
        semn=-1;
        c=nextch();
    }
    while('0'<=c && c<='9'){
        a=a*10+c-'0';
        c=nextch();
    }
    return a*semn;
}

#define MAXN 20000005
int heap[MAXN+1], last;

inline int Heap_father(int p){
    return p/2;
}
inline int Heap_leftson(int p){
    return 2*p;
}
inline int Heap_rightson(int p){
    return 2*p+1;
}
inline void Heap_Swap(int p1, int p2){
    int aux=heap[p1];
    heap[p1]=heap[p2];
    heap[p2]=aux;
}
inline void Heap_upheap(int p){
    while(Heap_father(p)>0 && heap[p]<heap[Heap_father(p)]){
        Heap_Swap(p, Heap_father(p));
        p=Heap_father(p);
    }
}
inline void Heap_downheap(int p){
    int flag=1;
    int ts=-1;
    while(flag){
        ts=-1;
        if(Heap_leftson(p)>last)
            flag=0;
        else{
            if(heap[Heap_leftson(p)]<heap[p])
                ts=Heap_leftson(p);
            if(Heap_rightson(p)<=last && heap[Heap_rightson(p)]<heap[Heap_leftson(p)] && heap[Heap_rightson(p)]<heap[p])
                ts=Heap_rightson(p);
            if(ts==-1)
                flag=0;
            else{
                Heap_Swap(p, ts);
                p=ts;
            }
        }
    }
}
inline void Heap_insert(int val){
    heap[++last]=val;
    Heap_upheap(last);
}
inline void Heap_erase(int poz){
    //int p=pos[poz];
    int p=poz;
    Heap_Swap(p, last);
    last--;
    if(Heap_father(p)>0 && heap[p]<heap[Heap_father(p)])
        Heap_upheap(p);
    else
        Heap_downheap(p);
}

int main(){
    fi=fopen("interclasari.in","r");
    fo=fopen("interclasari.out","w");
    int k=nextnum();
    int s=0;
    int ind=0;
    for(int i=0;i<k;i++){
        int x=nextnum();
        s+=x;
        for(int j=0;j<x;j++){
            int y=nextnum();
            Heap_insert(y);
        }
    }
    fprintf(fo,"%d\n", s);
    while(s>0){
        fprintf(fo,"%d ", heap[1]);
        //printf("%d %d\n", heap[2], heap[3]);
        Heap_erase(1);
        s--;
    }
    fclose(fi);
    fclose(fo);
    return 0;
}