Submission #433433

#	Time	Username	Problem	Language	Result	Execution time	Memory
433433		someone	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	818 ms	97224 KiB

scrivener

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

const int T = 20, N = 1 << T;

struct Node {
    char l;
    bool isLetter;
    int nbL, preL[T];
};

int last = 0;
vector<Node> node;

void Init() {
    node.push_back({' ', false, 0});
}

void info() {
    for(int i = 0; i <= last; i++)
        cout << node[i].l << ' ';
    cout << '\n';
    for(int i = 0; i <= last; i++)
        cout << node[i].preL[0] << ' ';
    cout << '\n';
    for(int i = 0; i <= last; i++)
        cout << node[i].nbL << ' ';
    cout << "\n\n";
}

void TypeLetter(char L) {
    int act = node.size();
    node.push_back({L, true});

    if(node[last].isLetter) {
        node[act].preL[0] = last;
        for(int i = 1; i < T; i++)
            node[act].preL[i] = node[node[act].preL[i-1]].preL[i-1];
    } else {
        for(int i = 0; i < T; i++)
            node[act].preL[i] = node[last].preL[i];
    }
    node[act].nbL = node[node[act].preL[0]].nbL + 1;
    last = act;
    //cout << "T\n";
    //info();
}

void UndoCommands(int U) {
    int act = node.size();
    node.push_back({' ', false});
    int pre = act - U - 1;

    if(node[pre].isLetter) {
        node[act].preL[0] = pre;
        for(int i = 1; i < T; i++)
            node[act].preL[i] = node[node[act].preL[i-1]].preL[i-1];
    } else {
        for(int i = 0; i < T; i++)
            node[act].preL[i] = node[pre].preL[i];
    }
    node[act].nbL = node[node[act].preL[0]].nbL + 1;
    last = act;
    //cout << "U\n";
    //info();
}

char GetLetter(int P) {
    int act = last;
    P = node[act].nbL - P - 1;
    //cout << "P " << node[act].nbL - P - 1 << ' ' << P << '\n';
    //info();
    for(int i = T-1; i > -1; i--)
        if(P >= (1 << i)) {
            act = node[act].preL[i];
            P -= 1 << i;
        }
    return node[act].l;
}

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