Cod sursa(job #2729206)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 24 martie 2021 14:00:57
Problema Coduri Huffman Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "huffman.in" );
ofstream fout( "huffman.out" );

const int NMAX = 1000005;

int n, nr_nodes;
int frec[NMAX];
int lf[2 * NMAX], rg[2 * NMAX];
queue < pair<int,int> > q1, q2;
string current;
long long lg;
long long val[NMAX];
int sz[NMAX];

long long Str_to_Int( string s ) {
    long long ans = 0;
    long long _aux = 1;

    for( int i = s.size() - 1; i >= 0; --i ) {
        ans += ( s[i] == '1' ) * _aux;
        _aux = ( _aux << 1 );
    }
    return ans;
}

void Dfs( int nod ) {
    if( lf[nod] == 0 && rg[nod] == 0 ) {
        lg += 1LL * frec[nod] * current.size();
        val[nod] = Str_to_Int( current );
        sz[nod] = current.size();
        return;
    }

    current.push_back( '0' );
    Dfs( lf[nod] );
    current.pop_back();

    current.push_back( '1' );
    Dfs( rg[nod] );
    current.pop_back();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    fin >> n;
    for( int i = 1; i <= n; ++i )
        fin >> frec[i];

    for( int i = 1; i <= n; ++i )
        q1.push( { i, frec[i] } );

    nr_nodes = n;
    while( q1.size() + q2.size() > 1 ) {
        int nod1, c1, nod2, c2;

        if( q2.empty() || ( !q1.empty() && q1.front().second < q2.front().second )) {
            nod1 = q1.front().first;
            c1 = q1.front().second;
            q1.pop();
        }
        else {
            nod1 = q2.front().first;
            c1 = q2.front().second;
            q2.pop();
        }

        if( q2.empty() || ( !q1.empty() && q1.front().second < q2.front().second )) {
            nod2 = q1.front().first;
            c2 = q1.front().second;
            q1.pop();
        }
        else {
            nod2 = q2.front().first;
            c2 = q2.front().second;
            q2.pop();
        }

        ++nr_nodes;
        lf[nr_nodes] = nod1;
        rg[nr_nodes] = nod2;

        q2.push( { nr_nodes, c1 + c2 } );
    }

    int root;
    if( !q1.empty() ) root = q1.front().first;
    else root = q2.front().first;

    Dfs( root );

    //for( int i = 1; i <= nr_nodes; ++i )
    //    fout << lf[i] << ' ' << rg[i] << '\n';

    fout << lg << '\n';
    for( int i = 1; i <= n; ++i )
        fout << sz[i] << ' ' << val[i] << '\n';


    return 0;
}