Submission #883251

#	Time	Username	Problem	Language	Result	Execution time	Memory
883251		JakobZorz	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1080 ms	144784 KiB

scrivener

#include<iostream>
using namespace std;

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

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

void Init(){
    root=new Trie;
    strs[0]=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]->par=strs[curr];
        strs[curr]->ch[l]->c=L;
    }
    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];
    while(ct->depth>P+1)
        ct=ct->par;
    return ct->c;
}

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