Cod sursa(job #773661)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 2 august 2012 12:25:20
Problema Coduri Huffman Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include<cstdio>
long long q[2000000];
int n,i,j,k,r[2000000],s[1000001],d[1000001];
short p[2000000];
int main()
{freopen("huffman.in","r",stdin);
freopen("huffman.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
       scanf("%d",&r[i]),q[i]=33000;
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]=k++,d[i]=k++;
else
if(q[j+1]<=r[k]||k>n)
       q[i]=q[j]+q[j+1],s[i]=n+j++,d[i]=n+j++;
else
       q[i]=r[k]+q[j],s[i]=k++,d[i]=n+j++;
printf("%lld\n",q[0]);
for(k=j=1,i=2*n-1;k<=j;i=r[k++])
if(i>n)
       i-=n,p[s[i]]=p[d[i]]=p[i+n]+1,q[s[i]]=2*q[i+n],q[d[i]]=q[s[i]]+1,r[j++]=s[i],r[j++]=d[i];
for(i=1;i<=n;i++)
       printf("%d %lld\n",p[i],q[i]);
return 0;}