Submission #1000694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000694		ProtonDecay314	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	544 ms	262144 KiB

scrivener

/*
Eyoo it's a persistent dynamic array!! :D
For the version history, all I need to do is to
maintain a dynamic array, and then
the undo command is just appending the previous
state to the array
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;

// For the dynamic array, I will use an INFINITE array
class Array {
    private:
        char _v;
        Array* _odd;
        Array* _even;
    public:
        Array(char a_v, Array* a_odd, Array* a_even): _v(a_v), _odd(a_odd), _even(a_even) {};

        char v() {
            return _v;
        }

        Array* odd() {
            if(_odd == nullptr) _odd = new Array(' ', nullptr, nullptr);
            return _odd;
        }

        Array* even() {
            if(_even == nullptr) _even = new Array(' ', nullptr, nullptr);
            return _even;
        }

        char get(int i) {
            if(i == 0) return _v;
            else if(i & 1) return odd()->get((i - 1) >> 1);
            else return even()->get((i - 1) >> 1);
        }

        Array* set(int i, char c) {
            if(i == 0) return new Array(c, _odd, _even);
            else if(i & 1) return new Array(_v, odd()->set((i - 1) >> 1, c), _even);
            else return new Array(_v, _odd, even()->set((i - 1) >> 1, c));
        }
};

class VersionedArray {
    private:
        vector<int> _sizes;
        vector<Array*> _stack;
    public:
        VersionedArray() {};

        inline void push_version(Array* v) {
            _stack.push_back(v);
        }

        inline void push_size(int size) {
            _sizes.push_back(size);
        }

        inline int num_versions() {
            return _stack.size();
        }

        inline Array* get_version(int i) {
            return _stack[i];
        }

        inline Array* get_past_version(int i) {
            return get_version(num_versions() - i - 1);
        }

        inline Array* top() {
            return _stack[num_versions() - 1];
        }

        inline int get_past_size(int i) {
            return _sizes[num_versions() - i - 1];
        }

        inline int top_size() {
            return _sizes[num_versions() - 1];
        }

        static VersionedArray create() {
            Array* first = new Array(' ', nullptr, nullptr);

            VersionedArray instance;
            instance.push_version(first);
            instance.push_size(0);

            return instance;
        }
};

VersionedArray versions;

void Init() {
    versions = VersionedArray::create();
}

void TypeLetter(char L) {
    int prev_top_size = versions.top_size();
    versions.push_size(prev_top_size + 1);
    versions.push_version(versions.top()->set(prev_top_size, L));
}

void UndoCommands(int U) {
    versions.push_size(versions.get_past_size(U));
    versions.push_version(versions.get_past_version(U));
}

char GetLetter(int P) {
    return versions.top()->get(P);
}

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