Submission #1000732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000732		ProtonDecay314	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	410 ms	137532 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) {
            if(par == nullptr) return;
            update_par(par);
        }

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

        void update_par(Node* par) {
            ptrs[0] = par;
            construct_jump_ptrs();
        }

        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);
    Node* first = new Node('L', nullptr);
    first->update_par(first);
    hist.push_back(first);
    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: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40