Submission #224029

#	Time	Username	Problem	Language	Result	Execution time	Memory
224029		Lawliet	Parrots (IOI11_parrots)	C++14	Compilation error	0 ms	0 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 true;
		}

		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;
};

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[])
{
	buildPowers();
	buildBinomials();

	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 "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 true;
		}

		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--;
	}
}

Compilation message (stderr)

/tmp/ccua75F8.o: In function `main':
grader_decoder.cpp:(.text.startup+0x1f6): undefined reference to `decode(int, int, int*)'
/tmp/ccDZwhZD.o: In function `encode(int, int*)':
decoder.cpp:(.text+0x14c8): undefined reference to `send(int)'
decoder.cpp:(.text+0x17bf): undefined reference to `send(int)'
collect2: error: ld returned 1 exit status