Cod sursa(job #818643)

Utilizator ahmed.abdraboahmed.abdrabo ahmed.abdrabo Data 17 noiembrie 2012 19:29:41
Problema Coduri Huffman Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.77 kb
#include <cstdio>
#include <deque>
#include <cassert>
#include <vector>
#include <iostream>

using namespace std;

inline int next_int() {
	int n = 0;
	char c = getchar_unlocked();
	while (!('0' <= c)) {
		c = getchar_unlocked();
	}
	while ('0' <= c) {
		n = n * 10 + c - '0';
		c = getchar_unlocked();
	}
	return n;
}

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

long long n, sum;
int Q1_front = 1, Q1_back = 1, Q2_front = 1, Q2_back = 1;
int root;
char fr[1000001];
long long sc[1000001];
node_t A[2000002];
int Q1[1000001];
int Q2[1000001];

void dfs(const int & root, const long long & code, const char & depth) {
	if (A[root].i == 0) {
		sum += A[root].W;
		dfs(A[root].L, code << 1, depth + 1);
		dfs(A[root].R, code << 1 | 1, depth + 1);
	} else {
		fr[root] = depth;
		sc[root] = code;
	}
}

int main() {
	freopen("huffman.in", "r", stdin);
	freopen("huffman.out", "w", stdout);
	n = next_int();
	for (int i = 1; i <= n; i++) {
		A[i].W = next_int();
		A[i].i = i;
		Q1[Q1_back++] = i;
	}
	int k = n;
	while (Q1_back - Q1_front > 0 || Q2_back - Q2_front > 1) {
		int a = 0, b = 0;
		if (Q1_back - Q1_front == 0) {
			a = Q2[Q2_front++];
		} else if (Q2_back - Q2_front == 0) {
			a = Q1[Q1_front++];
		} else if (A[Q1[Q1_front]].W <= A[Q2[Q2_front]].W) {
			a = Q1[Q1_front++];
		} else {
			a = Q2[Q2_front++];
		}
		if (Q1_back - Q1_front == 0) {
			b = Q2[Q2_front++];
		} else if (Q2_back - Q2_front == 0) {
			b = Q1[Q1_front++];
		} else if (A[Q1[Q1_front]].W <= A[Q2[Q2_front]].W) {
			b = Q1[Q1_front++];
		} else {
			b = Q2[Q2_front++];
		}
		k++;
		A[k].W = A[a].W + A[b].W;
		A[k].i = 0;
		A[k].L = a;
		A[k].R = b;
		Q2[Q2_back++] = k;
	}
	root = k;
	dfs(root, 0, 0);
	printf("%lld\n", sum);
	for (int i = 1; i <= n; i++) {
		printf("%d %lld\n", fr[i], sc[i]);
	}
	return 0;
}