Submission #417010

#	Time	Username	Problem	Language	Result	Execution time	Memory
417010		Collypso	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	798 ms	67908 KiB

scrivener

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#define F first
#define S second
//#define endl '\n'
//#define int long long

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

using namespace std;

const int const_lg = 20;
const int max_n = 1e6 + 7;

struct node
{
    char val;
    int h, parent[const_lg + 1];

    node() { }

    node(char val_, int parent_, int h_)
    {
        val = val_, h = h_, parent[0] = parent_;
    }
};

node trie[max_n];
int commands[max_n];
int trie_pointer, commands_pointer;

void Init()
{
    trie[0] = {'#', 0, -1};
    for(int i = 1; i <= const_lg; i++) trie[0].parent[i] = 0;
    trie_pointer = commands_pointer = 0;
}

void TypeLetter(char L)
{
    int root = commands[commands_pointer];
    commands_pointer++, trie_pointer++;
    trie[trie_pointer] = {L, root, trie[root].h + 1};
    for(int i = 1; i <= const_lg; i++)
        trie[trie_pointer].parent[i] = trie[trie[trie_pointer].parent[i - 1]].parent[i - 1];
    commands[commands_pointer] = trie_pointer;
}

void UndoCommands(int U)
{
    commands_pointer++;
    commands[commands_pointer] = commands[commands_pointer - U - 1];
}

char GetLetter(int P)
{
    int v = commands[commands_pointer];
    for(int k = const_lg; k >= 0; k--)
        if (trie[trie[v].parent[k]].h >= P) v = trie[v].parent[k];
    return trie[v].val;
}

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