Submission #433432

#	Time	Username	Problem	Language	Result	Execution time	Memory
433432		someone	Crayfish scrivener (IOI12_scrivener)	C++14	0 / 100	496 ms	94712 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 TypeLetter(char L) {
    int act = node.size();
    node.push_back({L, true, node[last].nbL+1});

    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];
    }
    last = act;
}

void UndoCommands(int U) {
    int act = node.size();
    node.push_back({' ', false, node[last].nbL});
    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];
    }
    last = act;
}

char GetLetter(int P) {
    int act = last;
    for(int i = T-1; i > -1; i--)
        if(P >= (1 << i)) {
            act = node[i].preL[i];
            P -= 1 << i;
        }
    return node[act].l;
}

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