Submission #486321

#	Time	Username	Problem	Language	Result	Execution time	Memory
486321		alextodoran	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	565 ms	133508 KiB

scrivener

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int BITS = 20;

struct Node
{
    int length;
    char parentLetter;
    Node* ancestor[BITS];

    Node (char letter = '-')
    {
        length = 0;
        parentLetter = letter;
        for(int bit = 0; bit < BITS; bit++)
            ancestor[bit] = this;
    }
};

Node* root = new Node();

void Init ()
{
    ;
}

vector <Node*> nodes = {root};

void TypeLetter (char letter)
{
    Node* son = new Node(letter);
    son->ancestor[0] = nodes.back();
    son->length = son->ancestor[0]->length + 1;
    for(int bit = 1; bit < BITS; bit++)
    {
        if(son->ancestor[bit - 1] == root)
            son->ancestor[bit] = root;
        else
            son->ancestor[bit] = son->ancestor[bit - 1]->ancestor[bit - 1];
    }
    nodes.push_back(son);
}

void UndoCommands (int cnt)
{
    nodes.push_back(nodes.end()[- (1 + cnt)]);
}

char GetLetter (int pos)
{
    Node* node = nodes.back();
    for(int bit = BITS - 1; bit >= 0; bit--)
        if(node->length - (1 << bit) > pos)
            node = node->ancestor[bit];
    return node->parentLetter;
}

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