Submission #931997

#	Time	Username	Problem	Language	Result	Execution time	Memory
931997		AlphaMale06	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	506 ms	98776 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;

#define pb push_back

struct node{
    char c;
    int p[20];
    int h;
};

vector<node> trie;

node make(int par, char ch){
    node ret;
    ret.c=ch;
    ret.h=trie[par].h+1;
    ret.p[0]=par;
    for(int i=1; i<20; i++){
        ret.p[i]=trie[ret.p[i-1]].p[i-1];
    }
    return ret;
}


int cur=0;
const int N = 1000010;
int curs[N];
int cnt;

void Add(char c){
    curs[cnt]=trie.size();
    trie.pb(make(cur, c));
    cur=curs[cnt];
    cnt++;
}

char lift(int v, int to){
    int ret=v;
    for(int i=19; i>=0; i--){
        if(trie[trie[ret].p[i]].h >= to){
            ret=trie[ret].p[i];
        }
    }
    return trie[ret].c;
}

void TypeLetter(char c) {
    Add(c);
}

void UndoCommands(int num) {
    curs[cnt]=curs[cnt-1-num];
    cur=curs[cnt];
    cnt++;
}

char GetLetter(int ind) {
    return lift(cur, ind+1);
}

void Init() {
    node first;
    first.h=0;
    for(int i=0; i<20; i++)first.p[i]=0;
    first.c=0;
    trie.pb(first);
    curs[0]=0;
    cnt=1;
}

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