Submission #1189706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189706		jasonic	Crayfish scrivener (IOI12_scrivener)	C++20	0 / 100	154 ms	103960 KiB

scrivener

/*

what we can do is store the ending after each "operation" in a trie.

then, undo becomes "go back k+1 endings". this can be done with binary jumping

something like that

fuck it we vibe code ts

*/

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)

int endptr[1000005];
char letters[1000005];
int jump[1000005][25]; // log_2(1e6) = 20 (the size of log still impresses me to this day)
int depth[1000005];
int i = -1;
int opCnt = -1;

void Init() {
    // who even needs to initialize jack bro
    
    // nvm
    memset(jump, -1, sizeof(jump));
}

void TypeLetter(char L) {
    
    i++;
    opCnt++;

    if(opCnt != 0) {
        depth[i] = depth[endptr[opCnt]] + 1;
        jump[i][0] = endptr[opCnt]; // parent

        for(int j = 1; (1ll << j) <= depth[i]; j++) {
            jump[i][j] = jump[jump[i][j-1]][j-1];
        }
    } else {
        depth[i] = 0;
    }

    letters[i] = L;
    endptr[opCnt] = i;
}

void UndoCommands(int U) {
    opCnt++;
    endptr[opCnt] = endptr[opCnt - U];
}

char GetLetter(int P) {
    // note that depth + 1 gives us the length, so to find how much we have to go from the back of the string, we have to traverse...
    ll depthDiff = depth[endptr[opCnt]] - P;
    int end = endptr[opCnt];

    for(ll i = 22; i >= 0 && depthDiff > 0; i--) {
        if(depthDiff & (1ll<<i)) {
            end = jump[end][i];
            depthDiff -= (1ll<<i);
        }
    }

    return letters[end];
}

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