#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)(x.size() )
#define CTE 29
const int BASE = (1<<CTE);
using namespace std ;
struct bignum
{
vector<int> a ;
void print()
{
cout << "Printing this shit" << endl ;
for(auto e : a ) cout << e << " " ;
cout << endl ;
}
void trim()
{
while( sz(a) > 0 && a.back() == 0 ) a.pop_back() ;
}
bignum operator + (bignum other) const
{
bignum aux ;
for(int i = 0 , carry = 0 ; i < max(sz(other.a), sz(a)) || carry ; i++ )
{
int addOther = (i >= sz(other.a) ) ? 0 : other.a[i] ;
int addThis = (i >= sz(a) ) ? 0 : a[i] ;
aux.a.push_back( addOther + addThis + carry ) ;
carry = ( aux.a.back() >= BASE ) ;
if(carry) aux.a.back() -= BASE ;
}
return aux ;
}
bool operator < ( bignum other ) const
{
if( sz(a) != sz(other.a) ) return sz(a) < sz(other.a) ;
for(int i = sz(a) - 1 ; i >= 0 ; i-- )
if( a[i] != other.a[i] ) return a[i] < other.a[i] ;
return false ;
}
bool operator == (bignum other) const
{
return !(*this < other) && !(other < *this) ;
}
bool operator <= (bignum other) { return !(other < *this ) ; }
bignum operator - (bignum other )const
{
bignum aux ;
for(int i = 0 ,carry=0 ; i < max(sz(a), sz(other.a) ) ; i++ )
{
int myNumber = ( i >= sz(a) ) ? 0 : a[i] ;
int otherNumber = ( i >= sz(other.a) ) ? 0 : other.a[i] ;
aux.a.push_back( myNumber - otherNumber - carry ) ;
carry = ( aux.a.back() < 0 ) ;
if(carry ) aux.a.back() += BASE ;
}
aux.trim() ;
return aux ;
}
} ;
void encode(int N, int M[])
{
vector<int> ans(64*8,0) ;
for(int i = 0, filling = 0 ; i < N ; i++ )
{
for(int j= 0 ; j < 8 ; j++ , filling++ )
if( (M[i]&(1<<j) ) != 0 ) ans[filling] = 1 ;
}
bignum num ;
for(int i = 0 ; i < sz(ans) ; )
{
int j = i , curNum = 0 ;
while( j < sz(ans) && j-i < CTE )
{
curNum |= (1<<(j-i)) * ans[j] ;
j++ ;
}
i = j ;
num.a.push_back(curNum ) ;
}
vector< vector<bignum> > bin(600, vector<bignum>(600) ) ;
for(int i = 0 ; i < 600 ; i++ )
{
bin[i][0].a.push_back(1) ;
for(int j = 1 ; j <= i ; j++ ) bin[i][j] = bin[i-1][j-1] + bin[i-1][j] ;
}
int MAX = 256 + 5*N ;
num.trim() ;
bignum toAdd ;
toAdd.a.push_back(1) ;
num = num + toAdd ;
int separatorsLeft = 256 ;
vector<int> myString(MAX, 0 ) ;
for(int i = 0 ; i < MAX && separatorsLeft ; i++ )
{
if( bin[MAX-1-i][separatorsLeft] < num )
{
num = num - bin[MAX-i-1][separatorsLeft] ;
// cout <<"Printing binomial" << endl ;
// for(auto e : bin[MAX-1-i][separatorsLeft].a ) cout << e << " " ;
// cout << endl ;
myString[i] = 1 ;
separatorsLeft-- ;
}
}
for(int i = 0 , cnt = 0; i < MAX && cnt < 256 ; cnt++ )
{
int j = i ;
while( j < MAX && myString[j] == 0 ) j++ ;
for(int g = 0 ; g < j-i ; g++ ) send(cnt) ;
i = j + 1 ;
}
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define ll long long
#define sz(x) (int)(x.size() )
#define CTE 29
const int BASE = (1<<CTE);
using namespace std ;
struct bignum
{
vector<int> a ;
void print()
{
cout << "Printing this shit" << endl ;
for(auto e : a ) cout << e << " " ;
cout << endl ;
}
void trim()
{
while( sz(a) > 0 && a.back() == 0 ) a.pop_back() ;
}
bignum operator + (bignum other) const
{
bignum aux ;
for(int i = 0 , carry = 0 ; i < max(sz(other.a), sz(a)) || carry ; i++ )
{
int addOther = (i >= sz(other.a) ) ? 0 : other.a[i] ;
int addThis = (i >= sz(a) ) ? 0 : a[i] ;
aux.a.push_back( addOther + addThis + carry ) ;
carry = ( aux.a.back() >= BASE ) ;
if(carry) aux.a.back() -= BASE ;
}
return aux ;
}
bool operator < ( bignum other ) const
{
if( sz(a) != sz(other.a) ) return sz(a) < sz(other.a) ;
for(int i = sz(a) - 1 ; i >= 0 ; i-- )
if( a[i] != other.a[i] ) return a[i] < other.a[i] ;
return false ;
}
bool operator == (bignum other) const
{
return !(*this < other) && !(other < *this) ;
}
bool operator <= (bignum other) { return !(other < *this ) ; }
bignum operator - (bignum other )const
{
bignum aux ;
for(int i = 0 ,carry=0 ; i < max(sz(a), sz(other.a) ) ; i++ )
{
int myNumber = ( i >= sz(a) ) ? 0 : a[i] ;
int otherNumber = ( i >= sz(other.a) ) ? 0 : other.a[i] ;
aux.a.push_back( myNumber - otherNumber - carry ) ;
carry = ( aux.a.back() < 0 ) ;
if(carry ) aux.a.back() += BASE ;
}
aux.trim() ;
return aux ;
}
} ;
void decode(int N, int L, int X[])
{
vector< vector<bignum> > bin(600, vector<bignum>(600) ) ;
for(int i = 0 ; i < 600 ; i++ )
{
bin[i][0].a.push_back(1) ;
for(int j = 1 ; j <= i ; j++ ) bin[i][j] = bin[i-1][j-1] + bin[i-1][j] ;
}
int MAX = 5*N + 256 ;
vector<int> freq(257 , 0 ) ;
for(int i= 0 ; i < L ; i++ ) freq[ X[i] ]++ ;
vector<int> myString(MAX,0) ;
int cnt = 0 ;
for(int i = 1 ; i <= 256 ; i++ )
{
cnt += freq[i-1] ;
myString[cnt] = 1 ;
cnt++ ;
}
bignum num ;
int separatorsLeft = 256 ;
for(int i = 0 ; i < MAX ; i++ )
{
if( myString[i] == 0 ) continue ;
num = num + bin[MAX-1-i][separatorsLeft] ;
separatorsLeft-- ;
}
num.trim() ;
vector<int> ans(8*N,0) ;
int curBit = 0 ;
for(int i : num.a )
{
for(int j = 0 ; j < CTE ; j++, curBit++ )
if( (i&(1<<j) ) != 0 ) ans[curBit] = 1 ;
}
for(int i = 0 ; i < sz(ans) ;)
{
int val = 0 ;
for(int j = 0 ; j < 8 ; j++ , i++ )
val += (1<<j) * ans[i] ;
output(val) ;
}
}
