Submission #224034

#	Time	Username	Problem	Language	Result	Execution time	Memory
224034		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(string s = "")
		{
			while( !s.empty() )
			{
				num.push_back( s.back() - '0' );
				s.pop_back();
			}
		}
 
		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;
 
				if( ans.digit(i) >= 10 )
				{
					acc = 1;
					ans.change( i , 10 );
				}
			}
 
			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:
 
		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(string s = "")
		{
			while( !s.empty() )
			{
				num.push_back( s.back() - '0' );
				s.pop_back();
			}
		}
 
		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; }
 
		void print()
		{
			for(int i = num.size() - 1 ; i >= 0 ; i--)
				printf("%d",num[i]);
 
			printf("\n");
		}
 
		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;
 
				if( ans.digit(i) >= 10 )
				{
					acc = 1;
					ans.change( i , 10 );
				}
			}
 
			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:
 
		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;
	BigNum binary;
 
	for(int i = 8*N - 1 ; i >= 0 ; i--)
		binary.insert( 0 );
 
	for(int i = 8*N - 1 ; i >= 0 ; i--)
	{
		BigNum aux = cur + pot[i];
 
		if( aux <= sum )
		{
			cur = aux;
			binary.change( i , -1 );
		}
	}
 
	for(int i = 0 ; i < N ; i++)
	{
		int v = 0;
 
		for(int j = 0 ; j < 8 ; j++)
			if( binary.digit( 8*i + j ) == 1 ) v += (1 << j);
 
		output( v );
	}
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:111:15: error: 'hasInit' cannot be used as a function
  if( !hasInit() )
               ^

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:111:15: error: 'hasInit' cannot be used as a function
  if( !hasInit() )
               ^