Cod sursa(job #818525)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 17 noiembrie 2012 16:49:24
Problema Coduri Huffman Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>
#include <deque>
#include <cassert>
#include <vector>

using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

struct node_t {
	long long W;
	int i;
	node_t * L;
	node_t * R;
};

int n, sum;
deque<node_t*> A, Q;
node_t * root;
pair<int, int> ans[1000001];

void dfs(node_t * root, int code, int depth) {
	if (root == 0)
		return;
	if (root->i == -1) {
		sum += root->W;
		dfs(root->L, code * 2 + 0, depth + 1);
		dfs(root->R, code * 2 + 1, depth + 1);
	} else {
		ans[root->i] = make_pair(depth, code);
	}
}

int main() {
	freopen("huffman.in", "r", stdin);
	freopen("huffman.out", "w", stdout);
	n = next_int();
	for (int i = 1; i <= n; i++) {
		node_t * a = new node_t;
		a->W = next_int();
		a->i = i;
		A.push_back(a);
	}
	while (A.size() > 0 || Q.size() > 1) {
		node_t * p = new node_t;
		p->i = -1;
		node_t * a = 0;
		node_t * b = 0;
		if (A.size() == 0) {
			a = Q.front();
			Q.pop_front();
		} else if (Q.size() == 0) {
			a = A.front();
			A.pop_front();
		} else if (A.front()->W < Q.front()->W) {
			a = A.front();
			A.pop_front();
		} else {
			a = Q.front();
			Q.pop_front();
		}
		if (A.size() == 0) {
			b = Q.front();
			Q.pop_front();
		} else if (Q.size() == 0) {
			b = A.front();
			A.pop_front();
		} else if (A.front()->W < Q.front()->W) {
			b = A.front();
			A.pop_front();
		} else {
			b = Q.front();
			Q.pop_front();
		}
		p->W = a->W + b->W;
		p->L = a;
		p->R = b;
		Q.push_back(p);
	}
	root = Q.front();
	dfs(root, 0, 0);
	printf("%d\n", sum);
	for (int i = 1; i <= n; i++) {
		printf("%d %d\n", ans[i].first, ans[i].second);
	}
	return 0;
}