Submission #402976

#	Time	Username	Problem	Language	Result	Execution time	Memory
402976		Charis02	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	995 ms	15856 KiB

scrivener

#include<iostream>
#define MAX_N 1000004

using namespace std;

struct node{
    int par;
    int sqpar;
    int len;
    char c;
};

node trie[MAX_N];
int sz;
const int sqrt = 800;

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

    if(trie[cur].len%sqrt == 0)
        trie[cur].sqpar = par;
    else
        trie[cur].sqpar = trie[par].sqpar;

    return;
}

int get_ancestor(int cur,int x)
{
    while(trie[trie[cur].sqpar].len >= x)
        cur = trie[cur].sqpar;

    while(trie[cur].len > x)
        cur = trie[cur].par;

    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,P+1)].c;
}

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