Cod sursa(job #2768776)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 12 august 2021 09:31:05
Problema Coduri Huffman Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.92 kb
#include<stdio.h>
#define N 1000100
#define inf 1LL * 1000000000 * 1000000000
struct nod {
    long long v;
    int f[2];
}d[2*N];
int n,i,j,k,p,l[2],r[2],q[2][N],g[N];
long long b[N],m,s;
void D(int p,long long c,int n)
{
    if(d[p].f[0])
        D(d[p].f[0],c*2,n+1),D(d[p].f[1],c*2+1,n+1);
    else
        g[p]=n,b[p]=c;
}
int main()
{
    freopen("huffman.in","r",stdin),freopen("huffman.out","w",stdout),scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d",&d[i].v),q[0][i]=i;
    for(k=n,l[0]=l[1]=1,r[0]=n;l[0]+l[1]<=r[0]+r[1];s+=d[k].v,q[1][++r[1]]=k)
        for(++k,j=0;j<2;j++) {
            for(p=i=0,m=inf;i<2;i++)
                if(d[q[i][l[i]]].v<m&&l[i]<=r[i])
                    p=i,m=d[q[i][l[i]]].v;
            d[k].f[j]=q[p][l[p]],d[k].v+=d[q[p][l[p]]].v,l[p]++;
        }
    D(k,0,0),printf("%lld\n",s);
    for(i=1;i<=n;i++)
        printf("%d %lld\n",g[i],b[i]);
    return 0;
}