Submission #1000716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000716		ProtonDecay314	Crayfish scrivener (IOI12_scrivener)	C++17	0 / 100	194 ms	222552 KiB

scrivener

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

class Node {
    public:
        Node* ptrs[20]; // Jump Pointers
        char v;

        Node(char a_v, Node* par): v(a_v) {
            ptrs[0] = par;
        }

        void construct_jump_ptrs() {
            for(int i = 1; i < 20; i++) {
                ptrs[i] = ptrs[i - 1]->ptrs[i - 1];
            }
        }

        char at(int i, int size) {
            int actual_ind = size - i - 1;
            Node* cur_ptr = this;

            for(int j = 0; j < 20; j++) {
                if((actual_ind >> j) & 0b1) cur_ptr = cur_ptr->ptrs[j];
            }

            return cur_ptr->v;
        }
};

vector<Node*> hist;
vector<int> sizes;
int last_version_ind = -1;

void Init() {
    hist.reserve(1000001);
    sizes.reserve(1000001);
    hist.push_back(new Node(' ', nullptr));
    sizes.push_back(0);
    
    last_version_ind++;
}

void TypeLetter(char L) {
    sizes.push_back(sizes[last_version_ind] + 1);
    hist.push_back(new Node(L, hist[last_version_ind]));
    last_version_ind++;
}

void UndoCommands(int U) {
    sizes.push_back(sizes[last_version_ind - U]);
    hist.push_back(hist[last_version_ind - U]);
    last_version_ind++;
}

char GetLetter(int P) {
    return hist[last_version_ind]->at(P, sizes[last_version_ind]);
}

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