Cod sursa(job #782351)
#include<fstream>
#include<string>
using namespace std;
typedef struct w{int l,r;}tip;
typedef struct q{int v; int poz;}tip2;
tip arb[2000005];
tip2 a[1000001],st[1000001],sol[1000001];
long long sum;
string s;
ifstream fin("huffman.in");
ofstream fout("huffman.out");
inline void dfs(int nod,int s,int lev){
if (arb[nod].l==0){sol[nod].v=s; sol[nod].poz=lev;} else dfs(arb[nod].l,s,lev+1);
if (arb[nod].r==0){sol[nod].v=s; sol[nod].poz=lev;} else dfs(arb[nod].r,s+(1<<lev),lev+1);
}
int main(void){
int i,j,n,x,cap,coada,l,nrnod=0;
fin>>n; getline(fin,s); n=0;
getline(fin,s,char(EOF)); i=j=0; l=s.length();
while(j<l) {
x=0;
while(s[j]!='\n' && j<l)x=(x*10)+(s[j++]-'0');
a[++n].v=x; a[n].poz=n; ++j; arb[n].l=arb[n].r=0;
}
i=3; cap=1; coada=1; st[coada].v=a[1].v+a[2].v; sum=st[coada].v; nrnod=n;
st[coada].poz=nrnod+1; ++nrnod; arb[nrnod].l=a[1].poz; arb[nrnod].r=a[2].poz;
a[n+1].v=10000000000000LL;
while (i<=n+1) {
if ( st[cap].v<=a[i].v&&cap<=coada ) {--i; a[i]=st[cap]; ++cap;}
if ( st[cap].v<=a[i+1].v&&cap<=coada ) {--i; a[i]=a[i+1]; a[i+1]=st[cap]; ++cap;}
if (i<n){
sum+=a[i].v+a[i+1].v;
++coada; st[coada].v=a[i].v+a[i+1].v; ++nrnod;
st[coada].poz=nrnod; arb[nrnod].l=a[i].poz; arb[nrnod].r=a[i+1].poz;
}
i=i+2;
}
fout<<sum<<"\n";
dfs(nrnod,0,0);
for (i=1; i<=n; ++i) fout<<sol[i].poz<<" "<<sol[i].v<<"\n";
return(0);
}