Submission #224036

#	Time	Username	Problem	Language	Result	Execution time	Memory
224036		Lawliet	Parrots (IOI11_parrots)	C++14	100 / 100	173 ms	27904 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXP = 330;
const int MAXL = 260;
const int MAXB = 520;
const int MAXV = 600;

class BigNum
{
	public:

		BigNum() : base( 1000000000 ) {}

		int size() { return num.size(); }
		int digit(int i) { return num[i]; }
		void insert(int k) { num.push_back( k ); }
		void change(int i, int k) { num[i] -= k; }

		BigNum operator + (BigNum& aux)
		{
			BigNum ans;

			BigNum A = aux;
			BigNum B = *this;

			if( A.size() < B.size() ) swap( A , B );

			while( B.size() != A.size() )
				B.insert( 0 );

			int acc = 0;

			for(int i = 0 ; i < B.size() ; i++)
			{
				ans.insert( A.digit(i) + B.digit(i) + acc );
				acc = 0;

				int curDigit = ans.digit(i);

				if( curDigit >= base )
				{
					acc = curDigit/base;
					ans.change( i , acc*base );
				}
			}

			if( acc > 0 ) ans.insert( acc );

			return ans;
		}

		bool operator < (BigNum aux)
		{
			if( this->size() != aux.size() ) return this->size() < aux.size();

			for(int i = aux.size() - 1 ; i >= 0 ; i--)
				if( this->digit(i) != aux.digit(i) ) return this->digit(i) < aux.digit(i);

			return false;
		}

	private:

		int base;

		vector< int > num;
};

bool hasInit = false;

BigNum pot[MAXB];
BigNum dp[MAXV][MAXL];

void buildPowers()
{
	pot[0].insert( 1 );

	for(int i = 1 ; i < MAXB ; i++)
		pot[i] = pot[i - 1] + pot[i - 1];
}

void buildBinomials()
{
	for(int i = 0 ; i < MAXV ; i++)
		dp[i][0].insert( 1 );

	for(int i = 1 ; i < MAXV ; i++)
		for(int j = 1 ; j <= i && j < MAXL ; j++)
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
}

void encode(int N, int M[])
{
	if( !hasInit )
	{
		buildPowers();
		buildBinomials();

		hasInit = true;
	}

	BigNum binary;

	for(int i = 0 ; i < N ; i++)
		for(int j = 0 ; j < 8 ; j++)
			if( M[i] & (1 << j) ) binary = binary + pot[ 8*i + j ];

	int remainParrots = 5*N;

	BigNum sum;

	for(int i = -1 ; i < 255 ; i++)
	{
		int qtdParrots;
		int qtdNumbers = 256 - i - 1;

		for(qtdParrots = 0 ; qtdParrots <= remainParrots ; qtdParrots++)
		{
			BigNum aux = sum;
			aux = aux + dp[ remainParrots - qtdParrots + qtdNumbers - 1 ][ qtdNumbers - 1 ];

			if( binary < aux ) break;

			sum = aux;
		}

		remainParrots -= qtdParrots;

		if( i == -1 ) continue;

		for(int j = 1 ; j <= qtdParrots ; j++)
			send( i );
	}

	while( remainParrots > 0 )
	{
		send( 255 );
		remainParrots--;
	}
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXP = 330;
const int MAXL = 260;
const int MAXB = 520;
const int MAXV = 600;

class BigNum
{
	public:

		BigNum() : base( 1000000000 ) {}

		int size() { return num.size(); }
		int digit(int i) { return num[i]; }
		void insert(int k) { num.push_back( k ); }
		void change(int i, int k) { num[i] -= k; }

		BigNum operator + (BigNum& aux)
		{
			BigNum ans;

			BigNum A = aux;
			BigNum B = *this;

			if( A.size() < B.size() ) swap( A , B );

			while( B.size() != A.size() )
				B.insert( 0 );

			int acc = 0;

			for(int i = 0 ; i < B.size() ; i++)
			{
				ans.insert( A.digit(i) + B.digit(i) + acc );
				acc = 0;

				int curDigit = ans.digit(i);

				if( curDigit >= base )
				{
					acc = curDigit/base;
					ans.change( i , acc*base );
				}
			}

			if( acc > 0 ) ans.insert( acc );

			return ans;
		}

		bool operator <= (BigNum aux)
		{
			if( this->size() != aux.size() ) return this->size() < aux.size();

			for(int i = aux.size() - 1 ; i >= 0 ; i--)
				if( this->digit(i) != aux.digit(i) ) return this->digit(i) < aux.digit(i);

			return true;
		}

	private:

		int base;

		vector< int > num;
};

bool hasInit = false;

int freq[MAXL];

BigNum pot[MAXB];
BigNum dp[MAXV][MAXL];

void buildPowers()
{
	pot[0].insert( 1 );

	for(int i = 1 ; i < MAXB ; i++)
		pot[i] = pot[i - 1] + pot[i - 1];
}

void buildBinomials()
{
	for(int i = 0 ; i < MAXV ; i++)
		dp[i][0].insert( 1 );

	for(int i = 1 ; i < MAXV ; i++)
		for(int j = 1 ; j <= i && j < MAXL ; j++)
			dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
}

void decode(int N, int L, int X[])
{
	if( !hasInit )
	{
		buildPowers();
		buildBinomials();

		hasInit = true;
	}

	BigNum sum;

	int qtd = 5*N - L;

	for(int i = 0 ; i < qtd ; i++)
		sum = sum + dp[ 5*N - i + 256 ][ 256 ];

	for(int i = 0 ; i < L ; i++)
		freq[ X[i] ]++;

	int remainParrots = L;

	for(int i = 0 ; i < 255 ; i++)
	{
		int qtdNumbers = 256 - i - 1;

		while( freq[i] > 0 )
		{
			sum = sum + dp[ remainParrots + qtdNumbers - 1 ][ qtdNumbers - 1 ];

			freq[i]--;
			remainParrots--;
		}
	}

	BigNum cur;

	vector< int > binary;

	for(int i = 8*N - 1 ; i >= 0 ; i--)
	{
		BigNum aux = cur + pot[i];

		if( aux <= sum )
		{
			cur = aux;
			binary.push_back( 1 );
		}
		else binary.push_back( 0 );
	}

	reverse( binary.begin() , binary.end() );

	for(int i = 0 ; i < N ; i++)
	{
		int v = 0;

		for(int j = 0 ; j < 8 ; j++)
			if( binary[8*i + j] == 1 ) v += (1 << j);

		output( v );
	}
}

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19