Submission #402961

#	Time	Username	Problem	Language	Result	Execution time	Memory
402961		Charis02	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	778 ms	93352 KiB

scrivener

#include<iostream>
#define MAX_N 1000004

using namespace std;

struct node{
    int par[21];
    int len;
    char c;
};

node trie[MAX_N];
int sz;

void init_node(int cur,int par,char c)
{
    trie[cur].par[0] = par;

    for(int i = 1;i <= 20;i++)
        trie[cur].par[i]=-1;

    trie[cur].c = c;
    trie[cur].len = trie[par].len+1;

    return;
}

int jump(int cur,int x)
{
    if(trie[cur].par[x] != -1)
        return trie[cur].par[x];

    return trie[cur].par[x] = jump(jump(cur,x-1),x-1);
}

int get_ancestor(int cur,int x)
{
    for(int i = 20;i >= 0;i--)
    {
        if(x >= (1 << i))
            return get_ancestor(jump(cur,i),x-(1<<i));
    }

    return cur;
}

void Init()
{
    init_node(0,0,'-');
    trie[0].len = 0;
    sz = 1;
    return;
}

void TypeLetter(char L)
{
    init_node(sz,sz-1,L);
    sz++;

    return;
}

void UndoCommands(int U)
{
    trie[sz] = trie[sz-U-1];
    sz++;

    return;
}

char GetLetter(int P)
{
   // cout << "here " << P << " " << sz-1 << " " << trie[sz-1].len << " " << get_ancestor(sz-1,trie[sz-1].len-P-1) << endl;
    return trie[get_ancestor(sz-1,trie[sz-1].len-P-1)].c;
}

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