Cod sursa(job #2626925)

Utilizator etienAndrone Stefan etien Data 9 iunie 2020 02:24:19
Problema Coduri Huffman Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include<fstream>
#include<queue>
#include<algorithm>

using namespace std;

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

int n,i,x,s,nr;
queue<int>q1,q2;
long long val[2000001];
int st[2000001],dr[2000001];
void adauga(int x,int y)
{
    val[++nr]=val[x]+val[y];
    st[nr]=x;
    dr[nr]=y;
    q2.push(nr);
}

pair<int,pair<int,long long>>rez[2000001];
long long nr2;

int minim()
{
    if(q1.empty())
    {
        int x=q2.front();
        q2.pop();
        return x;
    }
    if(q2.empty())
    {
        int x=q1.front();
        q1.pop();
        return x;
    }
    if(val[q1.front()]<val[q2.front()])
    {
        int x=q1.front();
        q1.pop();
        return x;
    }
    else
    {
        int x=q2.front();
        q2.pop();
        return x;
    }
}

void dfs(int poz,long long val,int cnt)
{
    if(st[poz]==0&&dr[poz]==0)
        {
            nr2++;
            rez[nr2].first=poz;
            rez[nr2].second.first=cnt;
            rez[nr2].second.second=val;
        }
    else
    {
        dfs(st[poz],val*2,cnt+1);
        dfs(dr[poz],val*2+1,cnt+1);
    }
}
int main()
{
    fin>>n;
    for(i=1; i<=n; i++)
    {
        fin>>x;
        q1.push(i);
        nr++;
        val[nr]=x;
    }
    while(q1.size()+q2.size()>1)
    {
        int x=minim();
        int y=minim();
        adauga(x,y);
    }
    for(i=n+1; i<=nr; i++)
        s+=val[i];
    fout<<s<<"\n";
    dfs(nr,0,0);
    sort(rez+1,rez+nr2+1);
    for(i=1;i<=nr2;i++)
    {
        fout<<rez[i].second.first<<" "<<rez[i].second.second<<"\n";
    }
}