#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, 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 false;
}
bool operator == (BigNum aux) { return num == aux.num; }
bool operator <= (BigNum aux) { return (*this) == aux || (*this) < aux; }
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--;
}
}
#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; }
BigNum operator + (BigNum& aux)
{
BigNum ans;
BigNum A = aux, 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 false;
}
bool operator == (BigNum aux) { return num == aux.num; }
bool operator <= (BigNum aux) { return (*this) == aux || (*this) < aux; }
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 );
}
}
