Submission #432823

#	Time	Username	Problem	Language	Result	Execution time	Memory
432823		JeanBombeur	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1080 ms	82756 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;
    return;
}

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

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

void UndoCommands(int nb) {
    
    nb  ++;
    Letter[++ nbOperations] = '$';
    SzString[nbOperations] = SzString[nbOperations - nb];
    Add(nbOperations, nbOperations - nb);
    return;
}

char GetLetter(int nb) {

    int k = SzString[nbOperations] - nb;
    if (Letter[nbOperations] != '$')
    {
        if (-- k == 0)
            return Letter[nbOperations];
    }
    int cur = nbOperations;
    for (int i = LOG - 1; i >= 0; i --)
    {
        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: 0 / 26
• Subtask 5: 0 / 40