#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
static unsigned fib[46] = {
1U, 2U, 3U, 5U,
8U, 13U, 21U, 34U,
55U, 89U, 144U, 233U,
377U, 610U, 987U, 1597U,
2584U, 4181U, 6765U, 10946U,
17711U, 28657U, 46368U, 75025U,
121393U, 196418U, 317811U, 514229U,
832040U, 1346269U, 2178309U, 3524578U,
5702887U, 9227465U, 14930352U, 24157817U,
39088169U, 63245986U, 102334155U, 165580141U,
267914296U, 433494437U, 701408733U, 1134903170U,
1836311903U, 2971215073U
};
void encode_fib(unsigned x) {
char unsigned fibc[46] = { 0 };
++x;
int i = 45;
while (x < fib[i]) {
--i;
}
int j = i;
for (; i >= 0; --i) {
if (x >= fib[i]) {
x -= fib[i];
++fibc[i];
}
}
for (int i = 0; i <= j; ++i)
encode_bit(fibc[i]);
encode_bit(1);
}
template<typename T> using Vec = std::vector<T>;
Vec<int> bfs(int hub, int nv, const Vec<Vec<int>>& giraffe) {
const int invalid = -1;
Vec<int> dist(nv);
std::fill(dist.begin(), dist.end(), invalid);
std::queue<std::pair<int, int>> q; q.emplace(hub, 0);
while (!q.empty()) {
auto [u, distance] = q.front(); q.pop();
if (dist[u] != invalid) continue;
dist[u] = distance++;
for (const auto& v : giraffe[u]) {
q.emplace(v, distance);
}
}
return dist;
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
Vec<Vec<int>> giraffe(nv);
for (int i = 0; i < ne ; ++i) {
int u = v1[i];
int v = v2[i];
giraffe[u].push_back(v);
giraffe[v].push_back(u);
}
for (int hub = 0; hub < nh; hub++) {
Vec<int> distances = bfs(hub, nv, giraffe);
for (int i = 0; i < nv; ++i) {
encode_fib(distances[i]);
}
}
return;
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
static unsigned fib[46] = {
1U, 2U, 3U, 5U,
8U, 13U, 21U, 34U,
55U, 89U, 144U, 233U,
377U, 610U, 987U, 1597U,
2584U, 4181U, 6765U, 10946U,
17711U, 28657U, 46368U, 75025U,
121393U, 196418U, 317811U, 514229U,
832040U, 1346269U, 2178309U, 3524578U,
5702887U, 9227465U, 14930352U, 24157817U,
39088169U, 63245986U, 102334155U, 165580141U,
267914296U, 433494437U, 701408733U, 1134903170U,
1836311903U, 2971215073U
};
unsigned decode_fib(void) {
unsigned prev = 0, current = 0, i = 0, tally = 0;
while (prev = current, current = decode_bit(), !prev || !current) {
if (current) {
tally += fib[i];
}
++i;
}
return tally-1;
}
void decode(int nv, int nh) {
for (int hub = 0; hub < nh; hub++) {
for (int i = 0; i < nv; ++i) {
hops(hub, i, decode_fib());
}
}
}
