#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>
#include <cassert>
#include <queue>
#include <unordered_map>
#define PARROTS
#ifndef PARROTS_MAIN
#include "encoder.h"
#include "encoderlib.h"
#endif
template<typename T>
using Vec = std::vector<T>;
Vec<int> SplitInto2Bit(int N, int* message) {
Vec<int> ret;
for (int i = 0; i < N; ++i) {
for (int k = 0; k < 4; ++k) {
int a = (message[i]>>(2*k));
ret.push_back(a&3);
}
}
return ret;
}
Vec<int> MoreFrequentWord(const Vec<int>& vec) {
Vec<std::pair<int, int>> count_and_val{std::make_pair(0, 0), std::make_pair(0, 1), std::make_pair(0, 2), std::make_pair(0, 3)};
for (int num : vec) {
++count_and_val[num].first;
}
std::sort(count_and_val.begin(), count_and_val.end());
std::reverse(count_and_val.begin(), count_and_val.end());
int num = count_and_val[0].second + count_and_val[1].second*4 + count_and_val[2].second*16 + count_and_val[3].second*64;
if (count_and_val[0].first != count_and_val[1].first || count_and_val[0].first != count_and_val[2].first || count_and_val[0].first != count_and_val[3].first) {
for (int i = 0; i < 4; ++i) {
send(num);
}
} else {
return {0, 1, 2, 3};
}
return {count_and_val[0].second, count_and_val[1].second, count_and_val[2].second, count_and_val[3].second};
}
void encode(int N, int* message_8) {
auto message = SplitInto2Bit(N, message_8);
auto frequency = MoreFrequentWord(message);
Vec<int> inverse_f(4);
for (int i = 0; i < frequency.size(); ++i) {
inverse_f[frequency[i]] = i;
}
for (int i = 0; i < message.size(); ++i) {
int num = message[i];
assert(num>=0 && num<4);
int times = inverse_f[num];
while (times--) {
send(i);
}
}
}
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdint>
#include <cstdlib>
#include <cassert>
#include <queue>
#include <unordered_map>
#ifndef PARROTS_MAIN
#include "decoder.h"
#include "decoderlib.h"
#endif
#ifndef PARROTS
template<typename T>
using Vec = std::vector<T>;
#endif
Vec<int> decodeTransition(int order) {
Vec<int> trans(4);
for (int k = 0; k < 4; ++k) {
trans[k] = ((order>>(2*k))&3);
}
return trans;
}
void substituteWithTransition(const Vec<int>& trans, Vec<int>& decoded_2_bit) {
for (int& num : decoded_2_bit) {
num = trans[num];
}
}
void outputFrom2BitVector(const Vec<int>& vec) {
for (int i = 0; i < vec.size(); i += 4) {
int num = 0;
for (int k = 0; k < 4; ++k) {
int x = vec.at(i + k);
num |= (x<<(2*k));
}
output(num);
}
}
void decode(int N, int L, int* X) {
Vec<int> decoded_2_bit(4*N);
std::unordered_map<int, int> Count;
int order = 0 + 1*4 + 2*16 + 3*64;
for (int i = 0; i < L; ++i) {
++Count[X[i]];
if (Count[X[i]] >= 4) {
order = X[i];
Count[X[i]] -= 4;
}
}
for (auto item : Count) {
if (item.second > 0) {
decoded_2_bit.at(item.first) = item.second;
}
}
Vec<int> trans = decodeTransition(order);
substituteWithTransition(trans, decoded_2_bit);
outputFrom2BitVector(decoded_2_bit);
}
