ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1307. Архиватор

I'm stuck with WA 1
Послано yyll 11 июн 2021 13:12
Even after reading all the posts here. Please help.
1. assert program is shorter than input
2. assert no long lines in source code
3. split string literal into vectors
4. assert no '\r' but '\n' after reading input
5. output with std::cout and '\n'
6. many tests and asserts

===this is an example of archive===
might be overkill to use Huffman and base64
shorten variable names in actual archive
===================================
//CPP
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

int length = 37;
std::vector<std::string> encoded{
"7VKh",
"7lg="
};
std::unordered_map<std::string, char> table{
{"00", 'o'},
{"01", 'l'},
{"100", 'w'},
{"1010", ' '},
{"1011", '!'},
{"1100", 'd'},
{"1101", 'e'},
{"1110", 'h'},
{"1111", 'r'}
};

struct HuffmanTree {
    char ch;
    struct HuffmanTree* left;
    struct HuffmanTree* right;
    ~HuffmanTree() {
        delete left;
        delete right;
    }
};

void build_tree(HuffmanTree* root, std::string code, char ch)
{
    auto node{root};
    for (auto x : code)
        if (x == '1') {
            if (node->right == nullptr)
                node->right = new HuffmanTree();
            node = node->right;
        } else {
            if (node->left == nullptr)
                node->left = new HuffmanTree();
            node = node->left;
        }
    node->ch = ch;
}

char lookup(std::vector<bool>::iterator& it, const HuffmanTree* tree)
{
    auto node{tree};
    while (true) {
        if (node->left == nullptr)
            break;
        if (*it)
            node = node->right;
        else
            node = node->left;
        it++;
    }
    return node->ch;
}

void huffman_decode(std::vector<bool> bits, const HuffmanTree* tree)
{
    auto it{bits.begin()};
    while (it != bits.end())
        std::cout << lookup(it, tree);
}

int six(char c)
{
    if (c >= 'A' and c <= 'Z')
        return c-'A';
    if (c >= 'a' and c <= 'z')
        return c-'a' + 26;
    if (c >= '0' and c <= '9')
        return c-'0' + 52;
    if (c == '+')
        return 62;
    if (c == '/')
        return 63;
    return 0;
}

std::vector<std::string> base64_decode(std::vector<std::string> encoded)
{
    std::vector<std::string> decoded;
    for (auto s : encoded) {
        std::string t;
        auto i{0u};
        while (i < s.size()) {
            auto p0{six(s[i])};
            auto p1{six(s[i+1])};
            auto p2{six(s[i+2])};
            auto p3{six(s[i+3])};
            t.push_back((p0<<2) + ((p1&0x30)>>4));
            if (s[i+2] != '=')
                t.push_back(((p1&0x0f)<<4) + ((p2&0x3c)>>2));
            if (s[i+3] != '=')
                t.push_back(((p2&0x03)<<6) + p3);
            i += 4;
        }
        decoded.push_back(t);
    }
    return decoded;
}

std::vector<bool> string_to_bits(int n, std::vector<std::string> v)
{
    std::vector<bool> bits;
    for (auto s : v)
        for (auto byte : s)
            for (auto i{7}; i >= 0; i--)
                bits.push_back((byte >> i) & 1);
    while (int(bits.size()) > n)
        bits.pop_back();
    return bits;
}

int main()
{
    auto decoded{base64_decode(encoded)};
    auto bits{string_to_bits(length, decoded)};
    auto root{new HuffmanTree()};
    for (auto [code, ch] : table)
        build_tree(root, code, ch);
    huffman_decode(bits, root);
}
To admins: Is there any issue I should know about using python to write a //CPP archiver?
Послано yyll 3 фев 2022 22:56
For a much simpler algorithm, the c++ program got accepted easily. However, the python version still got WA#1.

Probably some I/O issue for the python interpreter.

Maybe newlines are handled differently for python "print(s, end='')" and c++ "std::cout << s".

Edited by author 04.02.2022 08:15