Cod sursa(job #2903348)

Utilizator anne_marieMessner Anne anne_marie Data 17 mai 2022 14:58:42
Problema Coduri Huffman Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <cstdio>
#include <fstream>
#include <queue>

using namespace std;

const int NMAX = 1e6;
ifstream fin("huffman.in");
ofstream fout("huffman.out");

int n;
long long lungime_totala;
long long arb[2 * NMAX + 5];
int dad[2 * NMAX + 5];
bool tip[2 * NMAX + 5];

queue<int> frunze;
queue<int> noduri;

int pop_min(queue<int> &q1, queue<int> &q2) {
    if(!q1.empty() && (q2.empty() || arb[q1.front()] <= arb[q2.front()])) {
        int poz_min = q1.front();
        q1.pop();
        return poz_min;
    }
    else {
        int poz_min = q2.front();
        q2.pop();
        return poz_min;
    }
}

void print_node(int poz) {
    int lungime = 0;
    long long cod = 0;
    long long p2 = 1;

    while(poz < 2 * n - 1) {
        lungime++;
        cod += p2 * tip[poz];
        poz = dad[poz];
        p2 <<= 1;
    }
    fout<<lungime<<" "<<cod<<endl;
}

int main() {
    fin>>n;
    for(int i = 1; i <= n; i++) {
        fin>>arb[i];
        frunze.push(i);
    }
    lungime_totala = 0;
    int last_node = n;

    while(frunze.size() + noduri.size() > 1) {
        // minime
        int poz_min1 = pop_min(frunze, noduri);
        int poz_min2 = pop_min(frunze, noduri);

        arb[ ++last_node ] = arb[poz_min1] + arb[poz_min2];
        lungime_totala += arb[last_node];
        dad[poz_min1] = dad[poz_min2] = last_node;
        tip[poz_min1] = false;
        tip[poz_min2] = true;

        noduri.push(last_node);
    }
    fout << lungime_totala<<endl;
    for(int i = 1; i <= n; i++)
        print_node(i);

    return 0;
}