Cod sursa(job #774154)
#include <stdio.h>
#define maxt 2100000
#define maxn 1050000
struct Tree { long long v; int left, right; } T[maxt];
int N, root, Q[maxn], L[maxn];
long long lg, B[maxn];
void read () ;
void buildTree () ;
void BF () ;
void DF (int i, int level, long long path) ;
int main ()
{
FILE *out; int i;
read () ;
buildTree () ;
DF (root, 0, 0L);
out = fopen("huffman.out", "w");
fprintf (out, "%lld\n", lg);
for(i = 0; i < N; ++i)
fprintf (out, "%d %lld\n", L[i], B[i]);
fclose(out);
return 0;
}
void DF (int i, int level, long long path)
{
if ( T[i].left != -1)
DF ( T[i].left, level + 1, path<<1 );
if ( T[i].right != -1)
DF ( T[i].right, level + 1, (path<<1) + 1 );
else if (T[i].left == -1)
{
L[ i ] = level;
B[ i ] = path;
lg += T[i].v * level;
}
}
void BF ()
{
}
void buildTree ()
{
int l[2], r[2], choose[2], pos[2], i, k;
k = N -1;
l[0] = l[1] = 0;
r[0] = N-1; r[1] = -1;
while (l[0] <= r[0] || l[1] < r[1])
{
i = -1;
if (l[0] <= r[0])
{
pos[0] = l[0]; choose[0] = 0; ++i;
if (l[0]+1 <= r[0])
{
pos[1] = l[0]+1; choose[1] = 0; ++i;
}
}
if (l[1] <= r[1])
{
if ( i == -1 || T[ pos[0] ].v > T[ Q[ l[1] ] ].v )
{
pos[1] = pos[0]; choose[1] = 0;
pos[0] = Q[ l[1] ]; choose[0] = 1;
if ( l[1]+1 <= r[1] && (i == -1 || T[ pos[1] ].v > T[ Q[ l[1]+1 ] ].v) )
{
pos[1] = Q[ l[1]+1 ]; choose[1] = 1;
}
}
else if ( i == 0 || T[ pos[1] ].v > T[ Q[ l[1] ] ].v)
{
pos[1] = Q[ l[1] ]; choose[1] = 1;
}
}
++l[ choose[0] ]; ++l[ choose[1] ];
T[++k].v = T[ pos[0] ].v + T[ pos[1] ].v;
T[k].left = pos[0];
T[k].right = pos[1];
Q[ ++r[1] ] = k;
}
root = Q[ l[1] ];
}
void read () {
int i; FILE *in = fopen ("huffman.in", "r");
fscanf (in, "%d", &N);
for (i = 0; i < N; ++i)
{
fscanf (in, "%lld", &T[i].v);
T[i].left = T[i].right = -1;
}
fclose (in);
}