Submission #1233045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233045		badge881	Crayfish scrivener (IOI12_scrivener)	C++20	34 / 100	385 ms	327680 KiB

scrivener

// chatGPT ?? no a good known of STL ... ;-}

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

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

    struct Node {
        bool isLeaf;
        char letter;
        shared_ptr<Node> left;
        shared_ptr<Node> right;

        // Constructeur feuille
        Node(char l = 0) : isLeaf(true), letter(l), left(nullptr), right(nullptr) {}

        // Constructeur nœud interne
        Node(shared_ptr<Node> lft, shared_ptr<Node> rgt)
            : isLeaf(false), letter(0), left(lft), right(rgt) {}

        // Copie
        Node(const Node& other) : isLeaf(other.isLeaf), letter(other.letter),
            left(other.left), right(other.right) {}
    };

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

    persistantTab() = default;
    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>(head, nullptr);
            newTab.size *= 2;
        }

        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> {
                stack<tuple<shared_ptr<Node>, bool>> stk;

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

                shared_ptr<Node> current = node;
                int clow = low, chigh = high;

                while (chigh - clow > 1) {
                    int mid = (clow + chigh) / 2;
                    stk.emplace(current, pos >= mid);

                    if (!current->isLeaf) {
                        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;
                        }
                    } else {
                        // cas aberrant : transformer en nœud interne temporaire
                        current = make_shared<Node>();
                        chigh = mid;
                    }
                }

                shared_ptr<Node> updated = make_shared<Node>(l);

                while (!stk.empty()) {
                    auto [parent, isRight] = stk.top();
                    stk.pop();

                    shared_ptr<Node> copy = make_shared<Node>(*parent);
                    if (!copy->isLeaf) {
                        if (isRight)
                            copy->right = updated;
                        else
                            copy->left = updated;
                    } else {
                        copy->isLeaf = false;
                        if (isRight) {
                            copy->left = nullptr;
                            copy->right = updated;
                        } else {
                            copy->left = updated;
                            copy->right = nullptr;
                        }
                    }

                    updated = copy;
                }

                return updated;
            };

        newTab.head = addLIter(newTab.head, L, newTab.countains - 1, 0, newTab.size);
        return newTab;
    }

    char getLetter(int pos) const {
        if (pos < 0 || pos >= countains)
            return 0;

        function<char(shared_ptr<Node>, int, int, int)> getLIter =
            [](shared_ptr<Node> node, int p, int low, int high) -> char {
                while (node) {
                    if (node->isLeaf && high - low == 1)
                        return node->letter;

                    if (!node->isLeaf) {
                        int mid = (low + high) / 2;
                        if (p < mid) {
                            node = node->left;
                            high = mid;
                        } else {
                            node = node->right;
                            low = mid;
                        }
                    } else {
                        return node->letter;
                    }
                }
                return 0;
            };

        return getLIter(head, pos, 0, size);
    }
};


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