Submission #64433

#	Time	Username	Problem	Language	Result	Execution time	Memory
64433		zubec	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1071 ms	137596 KiB

scrivener

//#include "grader.h"
#include <bits/stdc++.h>
char last;

struct node{
    char c;

    node *pr[23];
    int deep;
    node(){
        for (int i = 0; i <= 21; i++)
            pr[i] = nullptr;
        deep = 0;
    }
};

node* bor[1000100];

int cnt;

void Init(){
    cnt = 0;
    bor[0] = new node();
}


void TypeLetter(char L) {
    ++cnt;
    if (!bor[cnt])
        bor[cnt] = new node();
    bor[cnt]->c = L;
    bor[cnt]->pr[0] = bor[cnt-1];
    for (int i = 1; i <= 21; i++){
        bor[cnt]->pr[i] = (bor[cnt]->pr[i - 1] ? bor[cnt]->pr[i - 1]->pr[i - 1] : nullptr);
    }
    bor[cnt]->deep = bor[cnt-1]->deep+1;
}

void UndoCommands(int U) {
    ++cnt;
    bor[cnt] = bor[cnt-U-1];
}

char GetLetter(int P) {
    node* ver = bor[cnt];
    int h = ver->deep-P-1;
    for (int i = 21; i >= 0; i--){
        if (h - (1<<i) >= 0){
            h -= (1<<i);
            ver = ver->pr[i];
        }
    }
    return ver->c;

}

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