parrots.cpp

#include "grader.h"
#include "encoder.h"
#include "decoder.h"
#include <algorithm>
#include <vector>
#include <iostream>

// No communication/shared data between two namespaces please.
namespace Encoder
{
// Your encoder implementation goes here.
	using namespace std;
	
	typedef unsigned long long ullint;
	
	ullint mem[70][70];
	
	ullint binomial(int n, int k)
	{
		if (k < 0 || k > n)
			return 0;
		if (k == 0 || k == n)
			return 1;
		if (mem[n][k])
			return mem[n][k];
		return mem[n][k] = binomial(n - 1, k) + binomial(n - 1, k - 1);
	}
	
	void send_all(int head, ullint x, int cnt)
	{
		int left = cnt;
		
		for (int i = 32 + cnt - 2; i >= 0; --i)
		{
			if (x >= binomial(i, left))
			{
				send(head | (i - left + 1));
				x -= binomial(i, left);
				--left;
			}
		}
	}
	
	void encode(int n, int arr[])
	{
		const int BLOCK = (n + 7) / 8;
		for (int i = 0; i < 8; ++i)
		{
			ullint x = 0;
			int cnt = 0;
			for (int j = 0; j < BLOCK && BLOCK * i + j < n; ++j)
			{
				x |= ullint(arr[BLOCK * i + j]) << (8 * j);
				cnt += 37;
			}
			
			send_all(i << 5, x, cnt / 8);
		}
	}
};

// No communication/shared data between two namespaces please.
namespace Decoder
{
// Your decoder implementation goes here.
	using namespace std;
	
	typedef unsigned long long ullint;
	
	ullint mem[70][70];
	
	ullint binomial(int n, int k)
	{
		if (k < 0 || k > n)
			return 0;
		if (k == 0 || k == n)
			return 1;
		if (mem[n][k])
			return mem[n][k];
		return mem[n][k] = binomial(n - 1, k) + binomial(n - 1, k - 1);
	}
	
	void decode(int n, int l, int arr[])
	{
		const int BLOCK = (n + 7) / 8;
		
		vector<int> messages[8];
		
		for (int i = 0; i < l; ++i)
		{
			messages[arr[i] >> 5].push_back(arr[i] & 31);
		}
		
		for (int i = 0; i < 8; ++i)
		{
			sort(messages[i].begin(), messages[i].end());
			int cnt = messages[i].size();
			for (int j = 0; j < cnt; ++j)
				messages[i][j] += j;
			
			ullint x = 0;
			for (int j = 0; j < cnt; ++j)
				x += binomial(messages[i][j], j + 1);
			
			for (int j = 0; j < BLOCK && BLOCK * i + j < n; ++j)
				output((x >> (8 * j)) & 255);
		}
	}
};

// Called by grader. Do not modify.
void encode(int N, int M[]) {
	Encoder::encode(N, M);
}

void decode(int N, int L, int X[]) {
	Decoder::decode(N, L, X);
}