Pagini recente » Cod sursa (job #1601470) | Cod sursa (job #2865075) | Cod sursa (job #2345934) | Cod sursa (job #1141261) | Cod sursa (job #2417165)
#include <bits/stdc++.h>
using namespace std;
queue<pair<long long,int>> qin,qout;
pair<int,long long> ans[1000010];
int st[2000010],dr[2000010],n;
void dfs(int nod,int niv,long long val)
{
if(nod<=n)
{
ans[nod]={niv,val};
return;
}
dfs(st[nod],niv+1,val*2);
dfs(dr[nod],niv+1,val*2+1);
}
int main()
{
freopen("huffman.in","r",stdin);
freopen("huffman.out","w",stdout);
int x;
long long sol=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
qout.push({x,i});
}
for(int i=1;i<n;i++)
{
pair<long long,int> mn[2];
for(int j=0;j<2;j++)
{
if(qin.empty())
{
mn[j]=qout.front();
qout.pop();
}
else if(qout.empty())
{
mn[j]=qin.front();
qin.pop();
}
else if(qin.front().first<qout.front().first)
{
mn[j]=qin.front();
qin.pop();
}
else
{
mn[j]=qout.front();
qout.pop();
}
}
st[i+n]=mn[0].second;
dr[i+n]=mn[1].second;
sol+=mn[0].first+mn[1].first;
qin.push({mn[0].first+mn[1].first,i+n});
}
dfs(2*n-1,0,0);
printf("%lld\n",sol);
for(int i=1;i<=n;i++) printf("%d %lld\n",ans[i].first,ans[i].second);
return 0;
}