Pagini recente » Atasamentele paginii mastermage | Borderou de evaluare (job #1428353) | Cod sursa (job #765975)
Cod sursa(job #765975)
#include<fstream>
#define N 2000000
long long q[N];
int n,i,j,k,r[N],s[N],d[N],p[N];
int main()
{ifstream f("huffman.in");
ofstream g("huffman.out");
f>>n;
for(i=1;i<=n;i++)
f>>r[i],q[i]=N;
for(k=j=i=1;i<n;q[0]+=q[i++])
if(k<n&&r[k+1]<=q[j])
q[i]=r[k]+r[k+1],s[i+n]=k++,d[i+n]=k++;
else
if(q[j+1]<=r[k]||k>n)
q[i]=q[j]+q[j+1],s[i+n]=n+j++,d[i+n]=n+j++;
else
q[i]=r[k]+q[j],s[i+n]=k++,d[i+n]=n+j++;
g<<q[0]<<"\n";
for(k=j=1,i=2*n-1;k<=j;i=r[k++])
if(i>n)
p[s[i]]=p[d[i]]=p[i]+1,q[s[i]]=2*q[i],q[d[i]]=q[s[i]]+1,r[j++]=s[i],r[j++]=d[i];
for(i=1;i<=n;i++)
g<<p[i]<<" "<<q[i]<<"\n";
return 0;}