Pagini recente » Cod sursa (job #943094) | Cod sursa (job #482394) | Cod sursa (job #2740417) | Cod sursa (job #1460244) | Cod sursa (job #1789518)
#include <cstdio>
#include <cctype>
#define MAXK 20
#define MAXN 1000000
#define BUF_SIZE (1<<17)
int n, pos = BUF_SIZE, heap[1+MAXN*MAXK];
char buf[BUF_SIZE];
FILE *fin, *fout;
inline char getChar();
inline int getInt();
inline int father(int x){ return x/2;}
inline int son_left(int x){return x*2;}
inline int son_right(int x){ return x*2+1;}
inline void swap1(int x, int y){
int aux;
aux = heap[x];
heap[x] = heap[y];
heap[y] = aux;
}
inline void down(int x)
{
int p, q, f = 1;
while(son_left(x) <= n && f)
{
f = 0;
p = son_left(x);
q = son_right(x);
if(q <= n && heap[q] < heap[p])
p = q;
if(heap[p] < heap[x])
swap1(p, x), f = 1;
x = p;
}
}
inline void heapify()
{
int i;
for(i=n/2; i>=1; --i)
down(i);
}
int main()
{
fin = fopen("interclasari.in", "r");
fout = fopen("interclasari.out", "w");
int i, j, k, p;
k = getInt();
for(i=1; i<=k; ++i)
{
p = getInt();
for(j=1; j<=p; ++j)
heap[++n] = getInt();
}
heapify();
fprintf(fout, "%d\n", n);
while(n)
{
fprintf(fout, "%d ", heap[1]);
swap1(1, n);
n--;
down(1);
}
return 0;
}
inline char getChar(){
if(pos == BUF_SIZE) pos = 0, fread(buf, 1, BUF_SIZE, fin);
return buf[pos++];
}
inline int getInt(){
int nr = 0;
char c;
c = getChar();
while(!isdigit(c)) c = getChar();
while(isdigit(c))
{
nr = nr*10 + c -'0';
c = getChar();
}
return nr;
}