Submission #538278

#	Time	Username	Problem	Language	Result	Execution time	Memory
538278		timreizin	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	571 ms	165420 KiB

scrivener

#include <vector>
#include <array>
#include <string>

using namespace std;

struct Trie
{
    array<int, 26> empty;
    vector<array<int, 26>> child;
    vector<array<int, 21>> up;
    vector<int> len;
    string chars;

    Trie()
    {
        empty.fill(-1);
        child.push_back(empty);
        up.push_back(array<int, 21>());
        up[0].fill(0);
        len.push_back(0);
        chars.push_back(' ');
    }

    int add(int v, char c)
    {
        if (child[v][c - 'a'] == -1)
        {
            child[v][c - 'a'] = child.size();
            child.push_back(empty);
            up.push_back(array<int, 21>());
            up[child[v][c - 'a']][0] = v;
            for (int i = 1; i < 21; ++i) up[child[v][c - 'a']][i] = up[up[child[v][c - 'a']][i - 1]][i - 1];
            len.push_back(len[v] + 1);
            chars.push_back(c);
        }
        v = child[v][c - 'a'];
        return v;
    }

    char get(int v, int i)
    {
        i = len[v] - i - 1;
        for (int j = 20; j >= 0; --j) if (i & (1 << j)) v = up[v][j];
        return chars[v];
    }

};

Trie trie;
vector<int> pos{0};

void Init()
{

}

void TypeLetter(char L)
{
    pos.push_back(trie.add(pos.back(), L));
}

void UndoCommands(int U)
{
    //2
    pos.push_back(pos[(int)pos.size() - U - 1]);
}

char GetLetter(int P)
{
    return trie.get(pos.back(), P);
}

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