Submission #1144683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144683		Can_I_Put_ma_ballz	저장 (Saveit) (IOI10_saveit)	C++20	25 / 100	134 ms	10392 KiB

encoder

#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

using u8 = uint8_t;

void encode_byte(u8 bits) {
    for (int i = 0; i < 8; ++i)
        encode_bit((bits >> i) & 1);
}

void encode_varint(int x) {
    do {
        u8 byte = x & 0x7f;
        x >>= 7;
        if (x != 0)
            byte |= 0x80;
        encode_byte(byte);
    } while (x != 0);
}

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_varint(distances[i]);
        }
    }

    return;
}

decoder

#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"

using u8 = uint8_t;

u8 decode_byte() {
   u8 byte = 0;
   for (int i = 0; i < 8; ++i)
      byte |= decode_bit() << i;
   return byte;
}

int decode_varint() {
   int result = 0;
   u8 shift = 0;
   while (true) {
      u8 byte = decode_byte();
      result |= (byte & 0x7f) << shift;
      if ((byte & 0x80) == 0)
         break;
      shift += 7;
   }
   return result;
}

void decode(int nv, int nh) {
   for (int hub = 0; hub < nh; hub++) {
      for (int i = 0; i < nv; ++i) {
         hops(hub, i, decode_varint());
      }
   }
}

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