Cod sursa(job #628428)

Utilizator sunt_emoSunt emo sunt_emo Data 1 noiembrie 2011 13:16:28
Problema Coduri Huffman Scor 90
Compilator c Status done
Runda Arhiva educationala Marime 1.62 kb
#include <stdio.h>
#include <stdlib.h>
#define Inf 9000000000000000000

typedef struct Node {
    long long data;
    int ind;
    struct Node * left;
    struct Node * right;
} Node;

short p[1000010];
long long q[1000010];
long long lg=0;

void print (Node * k,int u,long long v)
{
    if (!k) return;
    if (!k->left&&!k->right) {
        p[k->ind]=u;
        q[k->ind]=v;
        lg+=u*k->data;
    }
    print (k->left,u+1,v<<1);
    print (k->right,u+1,(v<<1)+1);
}

int main () {
    freopen ("huffman.in","r",stdin);
    freopen ("huffman.out","w",stdout);
    int i,n,c1=0,c2=0,d2=0;
    scanf ("%d",&n);
    Node * t,*t1,*t2,*inf;
    Node ** k1=(Node**) malloc ((n+10)*sizeof (Node *));
    Node ** k2=(Node**) malloc (((n<<1)+10)*sizeof (Node *));
    for (i=0; i<n; i++) {
        t=(Node*) malloc (sizeof (Node));
        scanf ("%lld",&t->data);
        t->ind=i;
        t->left=0;
        t->right=0;
        k1[i]=t;
    }
    k1[n]=malloc (sizeof (Node));
    k1[n]->data=Inf;
    inf=malloc (sizeof (Node));
    inf->data=Inf;
    k2[0]=inf;
    while (1) {
        if (k1[c1]->data<=k2[c2]->data) t1=k1[c1++];
        else t1=k2[c2++];
        if (k1[c1]->data<=k2[c2]->data) t2=k1[c1++];
        else t2=k2[c2++];
        if (t2->data==Inf) break;
        t=(Node*) malloc (sizeof (Node));
        t->data=t1->data+t2->data;
        t->left=t1;
        t->right=t2;
        k2[d2++]=t;
        k2[d2]=inf;
    }
    print (k2[c2-1],0,0);
    printf ("%lld\n",lg);
    for (i=0; i<n; i++) printf ("%d %lld\n",p[i],q[i]);
    fclose (stdin); fclose (stdout);
    return 0;
}