Submission #314999

#	Time	Username	Problem	Language	Result	Execution time	Memory
314999		Ozy	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	709 ms	198264 KiB

scrivener

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

char last;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define lli long long int
#define debug(a) //cout << #a << " = " << a << endl

struct x{
    char letra;
    lli padre;
    lli nivel;
};


lli p,act,cont = 1;
x instruccion[1000002];
lli binaryUp[1000002][22];

void Init() {
    instruccion[0].nivel = 0;
    instruccion[0].padre = 0;
    instruccion[0].letra = 0;

//    rep(i, 0, 1000001) rep(j, 0, 21) binaryUp[i][j] = 0;
}

void TypeLetter(char L) {

    instruccion[cont].letra = L;
    instruccion[cont].padre = cont-1;
    instruccion[cont].nivel = instruccion[ instruccion[cont].padre ].nivel + 1;

    p = 0;
    binaryUp[cont][0] = instruccion[cont].padre;
    while (binaryUp [ binaryUp[cont][p] ][p] > 0) {
        binaryUp[cont][p+1] = binaryUp [ binaryUp[cont][p] ][p];
        p++;
    }

    cont++;
}

void UndoCommands(int U) {
    instruccion[cont] = instruccion[cont - U - 1];
    act = 0;
    rep(i,0,20) binaryUp[cont][i] = binaryUp[cont - U - 1][i];

    cont++;
}

char GetLetter(int P) {

    p = 0;
    act = cont - 1;
    P = instruccion[cont-1].nivel - P - 1;

    while (P > 0) {
        if ((P & 1) == 1) act = binaryUp[act][p];
        P /= 2;
        p++;
    }

    return instruccion[act].letra;
}

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