Pagini recente » Diferente pentru problema/produse intre reviziile 5 si 4 | Concursuri Virtuale | Borderou de evaluare (job #2438314) | Cod sursa (job #1701678)
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream f("huffman.in");
ofstream g("huffman.out");
int const NMax = 1001000;
long long V[2*NMax], C[2*NMax];
int G[2*NMax][3], L[2*NMax];
long long n, nr, lg;
queue <int> Q1, Q2;
void Read()
{
f>>n;
for(int i=1; i<=n; i++)
f>>V[i];
}
int GetMin()
{
int x, y;
if(Q1.size() && Q2.size()){
x = Q1.front(); y = Q2.front();
if(V[x] < V[y]){
Q1.pop();
return x;
}
else{
Q2.pop();
return y;
}
}
if(Q1.size()){
x = Q1.front();
Q1.pop();
return x;
}
y = Q2.front();
Q2.pop();
return y;
}
void DFS(int nod, long long cod, bool side)
{
if(G[nod][0] == 0){
C[nod] = (cod << 1) + side;
return;
}
lg += V[nod];
cod = (cod << 1) + side;
int son1, son2;
son1 = G[nod][0];
son2 = G[nod][1];
L[son1] = L[son2] = L[nod] + 1;
DFS(G[nod][0], cod, 0);
DFS(G[nod][1], cod, 1);
}
void Solve()
{
int i, j, x, y;
for(i=1; i<=n; i++)
Q1.push(i);
nr = n;
while(Q1.size() + Q2.size() > 1){
nr++;
x = GetMin();
y = GetMin();
V[nr] = V[x] + V[y];
Q2.push(nr);
G[nr][0] = x;
G[nr][1] = y;
}
DFS(nr, 0, 0);
}
void Print()
{
g<<lg<<"\n";
for(int i=1; i<=n; i++)
g<<L[i]<<" "<<C[i]<<"\n";
}
int main()
{
Read();
Solve();
Print();
return 0;
}