Pagini recente » Cod sursa (job #285248) | Cod sursa (job #2600815) | Cod sursa (job #1143575) | Cod sursa (job #2355988) | Cod sursa (job #1798583)
#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;
}