Submission #1144689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144689		otesunki	Saveit (IOI10_saveit)	C++20	25 / 100	122 ms	9768 KiB

encoder

#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;
}

decoder

#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());
      }
   }
}

• Subtask 1: 25 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25