Submission #432834

#	Time	Username	Problem	Language	Result	Execution time	Memory
432834		JeanBombeur	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	632 ms	86468 KiB

scrivener

#include <iostream>
#include <cstdio>
using namespace std;

//   <|°_°|>

const int MAX_OPERATIONS = (1000 * 1000 + 1);
const int LOG = (20);

char Letter[MAX_OPERATIONS];
int SzString[MAX_OPERATIONS];

int LastLetter[MAX_OPERATIONS][LOG];

int nbOperations = 0;

void Init() {
    Letter[0] = '$';
    SzString[0] = 0;
    LastLetter[0][0] = -1;
    return;
}

void Add(int noeud) {
    if (Letter[noeud - 1] != '$')
        LastLetter[noeud][0] = noeud - 1;
    else
        LastLetter[noeud][0] = LastLetter[noeud - 1][0];
    for (int i = 1; i < LOG; i ++)
    {
        LastLetter[noeud][i] = LastLetter[LastLetter[noeud][i - 1]][i - 1];
        if (LastLetter[noeud][i] < 0)
            return;
    }
    return;
}

void TypeLetter(char L) {
    
    Letter[++ nbOperations] = L;
    SzString[nbOperations] = SzString[nbOperations - 1] + 1;
    Add(nbOperations);
    return;
}

void UndoCommands(int nb) {
    
    nb  ++;
    Letter[++ nbOperations] = '$';
    SzString[nbOperations] = SzString[nbOperations - nb];
    if (Letter[nbOperations - nb] != '$')
        LastLetter[nbOperations][0] = nbOperations - nb;
    else
        LastLetter[nbOperations][0] = LastLetter[nbOperations - nb][0];
    return;
}

char GetLetter(int nb) {

    int k = SzString[nbOperations] - nb;
    int cur = nbOperations;
    if (Letter[nbOperations] == '$')
        cur = LastLetter[nbOperations][0];
    if (-- k == 0)
        return Letter[cur];
    for (int i = 0; i < LOG; i ++)
    {
        if (LastLetter[cur][i] < 0)
            return Letter[cur];
        if (k & (1 << i))
            cur = LastLetter[cur][i];
    }
    return Letter[cur];
}

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