#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
using namespace std;
void encode(int N, int M[]) {
vector<vector<long long>> dp(21, vector<long long>(16));
for (int i = 0; i < 16; ++i) {
dp[0][i] = 1;
}
for (int i = 1; i < 21; ++i) {
for (int j = 0; j < 16; ++j) {
for (int k = j; k < 16; ++k) {
dp[i][j] += dp[i - 1][k];
}
}
}
vector<long long> sum(21);
for (int i = 1; i < 21; ++i) {
sum[i] = sum[i - 1] + dp[i][0];
}
vector<int> a(M, M + N);
while (a.size() % 4) {
a.push_back(0);
++N;
}
for (int i = 0; i < N; i += 4) {
long long state = 0;
for (int j = 0; j < 4; ++j) {
state |= (long long) a[i + j] << (j * 8);
}
int len = 0;
while (state >= sum[len]) {
++len;
}
state -= sum[len - 1];
int last = 0;
for (int j = len - 1; ~j; --j) {
long long sum = 0;
for (int k = last; k < 16; ++k) {
if (state < sum + dp[j][k]) {
send(i * 4 + k);
state -= sum;
last = k;
break;
}
sum += dp[j][k];
}
}
}
}
#include <bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;
void decode(int N, int L, int X[]) {
vector<vector<long long>> dp(21, vector<long long>(16));
for (int i = 0; i < 16; ++i) {
dp[0][i] = 1;
}
for (int i = 1; i < 21; ++i) {
for (int j = 0; j < 16; ++j) {
for (int k = j; k < 16; ++k) {
dp[i][j] += dp[i - 1][k];
}
}
}
vector<long long> sum(21);
for (int i = 1; i < 21; ++i) {
sum[i] = sum[i - 1] + dp[i][0];
}
int n = N;
while (N % 4) {
++N;
}
for (int i = 0; i < N; i += 4) {
long long state = 0;
vector<int> sorted;
for (int j = 0; j < L; ++j) {
if (X[j] / 16 == i / 4) {
sorted.push_back(X[j] % 16);
}
}
sort(sorted.begin(), sorted.end());
int len = (int) sorted.size();
int last = 0;
for (int j = len - 1; ~j; --j) {
for (int k = last; k < sorted[len - 1 - j]; ++k) {
state += dp[j][k];
}
last = sorted[len - 1 - j];
}
state += sum[len - 1];
for (int j = 0; j < 4; ++j) {
if (i + j < n) {
output((state >> (j * 8)) & 255);
}
}
}
}
