Pagini recente » Cod sursa (job #2440047) | Cod sursa (job #1049256) | Cod sursa (job #2923952) | Cod sursa (job #2685292) | Cod sursa (job #372975)
Cod sursa(job #372975)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
const char iname[] = "huffman.in";
const char oname[] = "huffman.out";
typedef long long i64;
struct huffman_node {
i64 fr;
int index, l_index, r_index;
void set(i64 f, int i, int l, int r) {
fr = f;
index = i, l_index = l, r_index = r;
}
};
bool operator < (const huffman_node& a, const huffman_node& b) {
return a.fr < b.fr;
}
bool operator <= (const huffman_node& a, const huffman_node& b) {
return a.fr <= b.fr;
}
vector <huffman_node> Q; vector <int> lg; vector <i64> b;
void walk(int i, int length, i64 code) {
if (Q[i].l_index + Q[i].r_index == -2) {
assert(length <= 64);
assert(0 <= code && code <= (1LL << 60));
assert(Q[i].index < (int) b.size());
lg[Q[i].index] = length;
b[Q[i].index] = code;
}
if (Q[i].l_index >= 0)
walk(Q[i].l_index, length + 1, code * 2);
if (Q[i].r_index >= 0)
walk(Q[i].r_index, length + 1, code * 2 + 1);
}
int main(void) {
int n;
ifstream in(iname);
assert(in >> n);
Q.resize(2 * n);
for (int i = 0; i < n; ++ i) {
int fr;
assert(in >> fr);
assert(1 <= fr && fr <= 100000000);
Q[i].set(fr, i, -1, -1);
if (i > 0)
assert(Q[i - 1] <= Q[i]);
}
for (int i = 0, j = n, cnt_n = n; cnt_n < 2 * n - 1; ) {
vector <huffman_node> T;
for (int k = i; k < min(i + 2, n); ++ k)
T.push_back(Q[k]);
for (int k = j; k < min(j + 2, cnt_n); ++ k)
T.push_back(Q[k]);
sort(T.begin(), T.end());
assert(T.size() >= 2);
Q[cnt_n].set(T[0].fr + T[1].fr, cnt_n, T[0].index, T[1].index);
cnt_n ++;
(T[0].index < n) ? ++ i : ++ j;
(T[1].index < n) ? ++ i : ++ j;
}
lg.resize(n);
b.resize(n);
walk(2 * n - 2, 0, 0);
ofstream out(oname);
out << Q[2 * n - 2].fr << "\n";
for (int i = 0; i < n; ++ i)
out << lg[i] << " " << b[i] << "\n";
out.close();
return 0;
}