Submission #883252

#	Time	Username	Problem	Language	Result	Execution time	Memory
883252		JakobZorz	Crayfish scrivener (IOI12_scrivener)	C++14	74 / 100	838 ms	262144 KiB

scrivener

#include<iostream>
using namespace std;

struct Trie{
    Trie*ch[26],*par[20];
    int depth;
    char c;
    Trie(){
        for(int i=0;i<26;i++)
            ch[i]=nullptr;
        for(int i=0;i<20;i++)
            par[i]=nullptr;
        depth=0;
    }
};

int curr;
Trie*root;
Trie*strs[1000000];

void Init(){
    root=new Trie;
    strs[0]=root;
    for(int i=0;i<20;i++)
        root->par[i]=root;
}

void TypeLetter(char L){
    curr++;
    strs[curr]=strs[curr-1];
    int l=L-'a';
    if(strs[curr]->ch[l]==nullptr){
        strs[curr]->ch[l]=new Trie;
        strs[curr]->ch[l]->depth=strs[curr]->depth+1;
        strs[curr]->ch[l]->c=L;
        strs[curr]->ch[l]->par[0]=strs[curr];
        for(int i=1;i<20;i++)
            strs[curr]->ch[l]->par[i]=strs[curr]->ch[l]->par[i-1]->par[i-1];
    }
    strs[curr]=strs[curr]->ch[l];
}

void UndoCommands(int U){
    curr++;
    strs[curr]=strs[curr-U-1];
}

char GetLetter(int P){
    Trie*ct=strs[curr];
    for(int i=19;i>=0;i--){
        if(ct->par[i]->depth>P)
            ct=ct->par[i];
    }
    return ct->c;
}

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