Cod sursa(job #983643)
#include <fstream>
#include <queue>
using namespace std;
const int Nmax = 1000010;
#define val first
#define key second
typedef long long i64;
typedef pair<i64,int> Pair;
typedef struct
{
i64 val;
int left,right;
} huff;
ifstream F("huffman.in");
ofstream G("huffman.out");
int N,K;
int A[Nmax];
queue<Pair> fr;
queue<Pair> gr;
huff H[Nmax<<1];
i64 Out;
int lun[Nmax],code[Nmax];
void Get(int nod,i64 Key,int Depth)
{
if ( H[nod].left || H[nod].right ) Out += H[nod].val;
if ( nod <= N )
{
lun[nod] = Key;
code[nod] = Depth;
}
if ( H[nod].left != 0 ) Get(H[nod].left,Key*2+0,Depth+1);
if ( H[nod].right != 0 ) Get(H[nod].right,Key*2+1,Depth+1);
}
int main()
{
F>>N;
for (int i=1;i<=N;++i)
F>>A[i];
for (int i=1;i<=N;++i)
{
fr.push( make_pair( A[i] , i ) );
H[i].val = A[i];
H[i].right = H[i].left = 0;
}
K = N;
while ( gr.size() > 1 || fr.size() > 0 )
{
Pair p = make_pair( 0 , ++K );
if ( ( fr.front() <= gr.front() && fr.size() > 0 ) || ( fr.size() > 0 && gr.size() == 0 ) )
{
p.val += fr.front().val;
H[p.key].left = fr.front().key;
fr.pop();
}
else
{
p.val += gr.front().val;
H[p.key].left = gr.front().key;
gr.pop();
}
if ( ( fr.front() <= gr.front() && fr.size() > 0 ) || ( fr.size() > 0 && gr.size() == 0 ) )
{
p.val += fr.front().val;
H[p.key].right = fr.front().key;
fr.pop();
}
else
{
p.val += gr.front().val;
H[p.key].right = gr.front().key;
gr.pop();
}
H[p.key].val = p.val;
gr.push( p );
}
Get( K,0,0 );
G<<Out<<'\n';
for (int i=1;i<=N;++i)
{
G<<lun[i]<<' ';
G<<code[i]<<'\n';
}
}