제출 #1233041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1233041		badge881	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++20	34 / 100	374 ms	327680 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

struct persistantTab
{
    int size = 1, countains = 0;

    struct Node
    {
        char letter = 0;
        shared_ptr<Node> left = nullptr;
        shared_ptr<Node> right = nullptr;

        Node() = default;
        Node(char l) : letter(l) {}
        Node(char l, shared_ptr<Node> lft, shared_ptr<Node> rgt) : letter(l), left(lft), right(rgt) {}
        Node(const Node &other) : letter(other.letter), left(other.left), right(other.right) {}
    };

    shared_ptr<Node> head = make_shared<Node>();

    persistantTab() : head(new Node()), size(1), countains(0) {}
    persistantTab(shared_ptr<Node> h, int s, int c) : head(h), size(s), countains(c) {}
    persistantTab addLetter(char L) const
    {
        persistantTab newTab(head, size, countains + 1);
        if (newTab.countains > newTab.size)
        {
            newTab.head = make_shared<Node>(0, head, nullptr);
            newTab.size *= 2;
        }

        // function<Node *(Node *, char, int, int, int)> addL = [&](Node *node, char l, int pos, int low, int high) -> Node *
        // {
        //     if (!node)
        //         node = new Node();
        //     if (high - low == 1)
        //     {
        //         node->letter = l; // Set the letter at the position
        //         return node;      // Return the updated node
        //     }
        //     Node *newNode = new Node(node);
        //     int mid = (low + high) / 2;
        //     if (pos < mid)
        //         // Go left
        //         newNode->left = addL(node->left, l, pos, low, mid);
        //     else
        //         // Go right
        //         newNode->right = addL(node->right, l, pos, mid, high);
        //     return newNode;
        // };
        function<shared_ptr<Node>(shared_ptr<Node>, char, int, int, int)> addLIter = [](shared_ptr<Node>node, char l, int pos, int low, int high) -> shared_ptr<Node>
        {
            // Pile pour mémoriser le chemin parcouru (nœuds + intervalles)
            stack<tuple<shared_ptr<Node>, bool>> stk;

            if (!node)
                node = make_shared<Node>();

            auto current = node;
            int clow = low, chigh = high;

            // Descente jusqu'à la feuille
            while (chigh - clow > 1)
            {
                int mid = (clow + chigh) / 2;

                stk.emplace(current, pos >= mid); // bool: true => droite, false => gauche

                if (pos < mid)
                {
                    if (!current->left)
                        current->left = make_shared<Node>();
                    current = current->left;
                    chigh = mid;
                }
                else
                {
                    if (!current->right)
                        current->right = make_shared<Node>();
                    current = current->right;
                    clow = mid;
                }
            }

            // Mise à jour de la feuille
            auto updated = make_shared<Node>(*current);
            updated->letter = l;

            // Remontée en créant de nouveaux nœuds
            while (!stk.empty())
            {
                auto [parent, isRight] = stk.top();
                stk.pop();

                auto copy = make_shared<Node>(*parent);
                if (isRight)
                    copy->right = updated;
                else
                    copy->left = updated;

                updated = copy;
            }

            return updated;
        };
        newTab.head = addLIter(newTab.head, L, newTab.countains - 1, 0, newTab.size);
        return newTab;
    }
    char getLetter(int pos) const
    {
        // function<char(Node *, int, int, int)> getL = [&](Node *node, int p, int low, int high) -> char
        // {
        //     if (!node)
        //         return 0; // If the node is null, return 0 (no letter)
        //     if (high - low == 1)
        //         return node->letter; // Return the letter at the position
        //     int mid = (low + high) / 2;
        //     if (p < mid)
        //         // Go left
        //         return getL(node->left, p, low, mid);
        //     else
        //         // Go right
        //         return getL(node->right, p, mid, high);
        // };
        function<char(shared_ptr<Node>, int, int, int)> getLIter = [](shared_ptr<Node>node, int p, int low, int high) -> char
        {
            while (node)
            {
                if (high - low == 1)
                    return node->letter;

                int mid = (low + high) / 2;

                if (p < mid)
                {
                    // Aller à gauche
                    node = node->left;
                    high = mid;
                }
                else
                {
                    // Aller à droite
                    node = node->right;
                    low = mid;
                }
            }
            return 0; // Si on atteint un nœud nul
        };
        if (pos < 0 || pos >= countains)
            return 0; // If the position is out of bounds, return 0
        char l = getLIter(head, pos, 0, size);
        return l; // Convert to character
    }
};

vector<persistantTab> tabs;

void Init()
{
    // cout << "Init" << endl;
    tabs.push_back(persistantTab());
    // tabs.back().show();
    // cout << "Init done" << endl;
}

void TypeLetter(char L)
{
    // cout << "TypeLetter: " << L << endl;
    tabs.push_back(tabs.back().addLetter(L));
    // tabs.back().show();
    // cout << "TypeLetter done" << endl;
}

void UndoCommands(int U)
{
    // cout << "UndoCommands: " << U << endl;
    tabs.push_back(tabs[tabs.size() - 1 - U]);
    // tabs.back().show();
    // cout << "UndoCommands done" << endl;
}

char GetLetter(int P)
{
    return tabs.back().getLetter(P);
}

#ifdef HOME
int main()
{
    Init();
    int tmp;
    int cmd_num;
    tmp = scanf("%d", &cmd_num);
    assert(tmp == 1);

    int i;
    for (i = 0; i < cmd_num; i++)
    {
        char cmd;
        tmp = scanf(" %c", &cmd);
        assert(tmp == 1);
        if (cmd == 'T')
        {
            char letter;
            tmp = scanf(" %c", &letter);
            assert(tmp == 1);
            TypeLetter(letter);
        }
        else if (cmd == 'U')
        {
            int number;
            tmp = scanf("%d", &number);
            assert(tmp == 1);
            UndoCommands(number);
        }
        else if (cmd == 'P')
        {
            int index;
            char letter;
            tmp = scanf("%d", &index);
            assert(tmp == 1);
            letter = GetLetter(index);
            printf("ans : %c\n", letter);
        }
    }

    return 0;
}
#endif

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40