Submission #578667

#	Time	Username	Problem	Language	Result	Execution time	Memory
578667		MohamedFaresNebili	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	938 ms	98420 KiB

scrivener

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

        using namespace std;
        using namespace __gnu_pbds;

        using ll = long long;
        using ii = pair<int, int>;

        #define pb push_back
        #define pp pop_back
        #define ff first
        #define ss second

        typedef tree<int, null_type, less<int>, rb_tree_tag,
            tree_order_statistics_node_update> indexed_set;

        int N, P[1000005], par[1000005][22];
        vector<char> S(1000005, '_');
        vector<int> arr;

        void Init() {
            arr.pb(0); P[0] = 0;
        }
        void TypeLetter(char c) {
            N++; S[N] = c;
            par[N][0] = P[N - 1];
            for(int l = 1; l < 22; l++)
                par[N][l] = par[par[N][l - 1]][l - 1];
            P[N] = N;
            arr.pb(arr.back() + 1);
        }
        void UndoCommands(int x) {
            N++; P[N] = P[N - x - 1];
            par[N][0] = P[N];
            for(int l = 1; l < 22; l++)
                par[N][l] = par[par[N][l - 1]][l - 1];
            arr.pb(arr[arr.size() - x - 1]);
        }
        char GetLetter(int x) {
            x = arr.back() - x - 1;
            int K = P[N];
            for(int l = 0; l < 22; l++)
                if(x & (1 << l))
                    K = par[K][l];
            return S[K];
        }

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