#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;
int bits = 4;
int emp = 64 / pow(2, 8 - bits);
int pn = 5;
map<int, map<int, long long>> dp;
long long f(int num, int niv) {
if (niv == 0) return 1;
if (niv == 1 || num == 0) {
return num;
}
if (dp[num][niv] == 0) {
dp[num][niv] = f(num, niv - 1) + f(num - 1, niv);
}
return dp[num][niv];
}
void sendcode(long long code, int niv, int pre, vector<pair<long long, long long>> &posi) {
for (int t1 = niv; t1 >= 1; t1 --) {
for (int t2 = (1<<bits)-1; t2 >= 0; t2 --) {
if (code >= f(t2, t1)) {
send(pre + t2);
code -= f(t2, t1);
break ;
}
}
}
}
void empac(long long code, int pre, vector<pair<long long, long long>> &posi) {
for (int niv = 1; niv < posi.size(); niv ++) {
if (posi[niv].first <= code && code <= posi[niv].second) {
code -= posi[niv].first;
sendcode(code, niv, pre << bits, posi);
break ;
}
}
}
void encode(int n, int m[]) {
vector<pair<long long, long long>> posi = {{-1, -1}};
for (int t1 = 1; t1 <= emp*pn; t1 ++) {
posi.push_back({f((1<<bits)+1, t1 - 1) - 1, f((1<<bits)+1, t1 - 1) + f((1<<bits), t1) - 2});
}
int sup = (1<<(8-bits)) - 1;
int index = 0;
while (n >= emp) {
long long code = 0;
for (int t1 = 0; t1 < emp; t1 ++) {
code <<= 8;
code += m[index];
index ++;
}
empac(code, sup, posi);
n -= emp;
sup --;
}
if (n != 0) {
long long code = 0;
for (int t1 = 0; t1 < n; t1 ++) {
code <<= 8;
code += m[index];
index ++;
}
empac(code, sup, posi);
sup --;
}
return ;
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;
int bits = 4;
int emp = 64 / pow(2, 8 - bits);
int pn = 5;
map<int, map<int, long long>> dp;
long long f(int num, int niv) {
if (niv == 0) return 1;
if (niv == 1 || num == 0) {
return num;
}
if (dp[num][niv] == 0) {
dp[num][niv] = f(num, niv - 1) + f(num - 1, niv);
}
return dp[num][niv];
}
long long decod(vector<int> nums) {
long long sum = 0;
sort(nums.begin(), nums.end());
for (int t1 = 0; t1 < nums.size(); t1 ++) {
sum += f(nums[t1], t1+1);
}
return sum;
}
void decode(int n, int t, int cod[]) {
vector<pair<long long, long long>> posi = {{-1, -1}};
vector<int> ns(t);
for (int t1 = 1; t1 <= emp*pn; t1 ++) {
posi.push_back({f((1<<bits) + 1, t1 - 1) - 1, f((1<<bits) + 1, t1 - 1) + f((1<<bits), t1) - 2});
}
for (int t1 = 0; t1 < t; t1++) {
ns[t1] = cod[t1];
}
sort(ns.rbegin(), ns.rend());
int sup = (1<<(8-bits)) - 1;
int index = 0;
while (n >= emp) {
long long code = 0;
vector<int> nums;
while (index < t && sup == (ns[index] >> bits)) {
nums.push_back(ns[index] % (1<<bits));
index ++;
}
code = decod(nums) + posi[nums.size()].first;
n -= emp;
sup --;
vector<int> ax1;
ax1.clear();
for (int t1 = emp; t1 > 0; t1 --) {
ax1.push_back(code % 256);
code >>= 8;
}
for (int t1 = ax1.size() -1; t1 >= 0; t1 --) {
output(ax1[t1]);
}
}
if (n != 0) {
long long code = 0;
vector<int> nums;
while (index < t && sup == (ns[index] >> bits)) {
nums.push_back(ns[index] % (1<<bits));
index ++;
}
code = decod(nums) + posi[nums.size()].first;
vector<int> ax1;
for (int t1 = n; t1 > 0; t1 --) {
ax1.push_back(code % 256);
code >>= 8;
}
for (int t1 = ax1.size() -1; t1 >= 0; t1 --) {
output(ax1[t1]);
}
}
}
