#include <stdio.h>
#include <stdlib.h>

#define TRUE  1
#define FALSE 0

typedef char byte;

typedef struct 
{
    void*              parent;
    byte               isLeft;
    unsigned long long occurences;
    void*              child1;
    void*              child2;
} Letter;

void SiftDown(Letter** letterHeap, int heapLength, int position)
{
    Letter** heapInUse = letterHeap - 1;
    if(position <= heapLength)
    {
        int next1 = position * 2;
        int next2 = next1 + 1;

        if(next1 <= heapLength)
        {
            int bestIndex = next1;

            if(next2 <= heapLength)
            {
                if(heapInUse[next2]->occurences < heapInUse[bestIndex]->occurences)
                {
                    bestIndex = next2;
                }
            }

            if(heapInUse[bestIndex]->occurences < heapInUse[position]->occurences)
            {
                Letter* tmp = heapInUse[bestIndex];
                heapInUse[bestIndex] = heapInUse[position];
                heapInUse[position] = tmp;

                SiftDown(letterHeap, heapLength, bestIndex);
            }
        }
    }
}

Letter* DeleteBest(Letter** letterHeap, int* heapLength)
{
    Letter** heapInUse = letterHeap - 1;
    Letter* result = heapInUse[1];

    heapInUse[1] = heapInUse[*heapLength];
    (*heapLength)--;
    SiftDown(letterHeap, *heapLength, 1);

    return result;
}

void Percolate(Letter** letterHeap, int heapLength, int position)
{
    Letter** heapInUse = letterHeap - 1;
    if(position >= 1)
    {
        int prevPos = position / 2;
        if(prevPos >= 1)
        {
            if(heapInUse[position]->occurences < heapInUse[prevPos]->occurences)
            {
                Letter* tmp = heapInUse[position];
                heapInUse[position] = heapInUse[prevPos];
                heapInUse[prevPos] = tmp;

                Percolate(letterHeap, heapLength, prevPos);
            }
        }
    }
}

void InsertLetter(Letter** letterHeap, Letter* letter, int* heapLength)
{
    Letter** heapInUse = letterHeap - 1;

    (*heapLength)++;
    heapInUse[*heapLength] = letter;

    Percolate(letterHeap, *heapLength, *heapLength);
}

unsigned long long Huffman(Letter** letterHeap, int* heapLength)
{
    unsigned long long result = 0;

    while((*heapLength) != 1)
    {
        Letter* firstBest = DeleteBest(letterHeap, heapLength);
        Letter* secondBest = DeleteBest(letterHeap, heapLength);

        Letter* mergedLetter = (Letter*)malloc(sizeof(Letter));
        mergedLetter->occurences = firstBest->occurences + secondBest->occurences;
        mergedLetter->parent = NULL;
        mergedLetter->isLeft = FALSE;

        mergedLetter->child1 = firstBest;
        mergedLetter->child2 = secondBest;

        firstBest->parent = mergedLetter;
        firstBest->isLeft = TRUE;

        secondBest->parent = mergedLetter;
        secondBest->isLeft = FALSE;

        result += mergedLetter->occurences;

        InsertLetter(letterHeap, mergedLetter, heapLength);
    }

    return result;
}

void ShowLetter(FILE* fout, Letter* letter, int accumNumber, int index)
{
    if(letter->parent != NULL)
    {
        accumNumber += letter->isLeft << index;
        ShowLetter(fout, (Letter*)letter->parent, accumNumber, index + 1);
    }
    else
    {
        fprintf(fout, "%d %d\n", index, accumNumber);
    }
    
}

void DeleteLetters(Letter* parent)
{
    if(parent->child1 != NULL)
    {
        DeleteLetters((Letter*)parent->child1);
    }

    if(parent->child2 != NULL)
    {
        DeleteLetters((Letter*)parent->child2);
    }

    free(parent);
    parent = NULL;
}

int main(void)
{
    FILE* fin = fopen("huffman.in", "r");
    FILE* fout = fopen("huffman.out", "w");
    int i;
    int n;
    int heapLength = 0;
    Letter** codeLetters;
    Letter** letterHeap;

    fscanf(fin, "%d", &n);
    heapLength = n;
    
    codeLetters = (Letter**)malloc(sizeof(Letter*) * n);
    letterHeap = (Letter**)malloc(sizeof(Letter*) * n);

    for(i = 0; i < n; i++)
    {
        unsigned long long occurences;
        fscanf(fin, "%llu", &occurences);

        codeLetters[i] = (Letter*)malloc(sizeof(Letter));
        codeLetters[i]->parent = NULL;
        codeLetters[i]->occurences = occurences;
        codeLetters[i]->isLeft = FALSE;
        codeLetters[i]->child1 = NULL;
        codeLetters[i]->child2 = NULL;

        letterHeap[i] = codeLetters[i];
    }

    fprintf(fout, "%llu\n", Huffman(letterHeap, &heapLength));

    for(int i = 0 ; i < n; i++)
    {
        ShowLetter(fout, codeLetters[i], 0, 0);
    }

    // Don't forget about this!
    // Even though the algorighm doesn't give 100
    // it doesn't mean it shouldn't clean its' garbage.
    DeleteLetters(letterHeap[0]);

    free(codeLetters);
    codeLetters = NULL;
    free(letterHeap);
    letterHeap = NULL;

    fclose(fin);
    fclose(fout);

    return 0;
}