Submission #560498

#	Time	Username	Problem	Language	Result	Execution time	Memory
560498		Leo121	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	631 ms	182580 KiB

scrivener

#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)

using namespace std;

const int maxn = 1e6;
const int log2maxn = log2(maxn);

struct ura{
    int longitud;
    char letra;
    ura *ancestros[log2maxn + 1];
    ura(){
        longitud = 0;
        letra = '0';
        forn(i, 0, log2maxn){
            ancestros[i] = nullptr;
        }
    }
};
ura *movimientos[maxn + 1];
int idx;

void Init() {
    forn(i, 0, maxn){
        movimientos[i] = nullptr;
    }
    movimientos[0] = new ura();
    movimientos[0]->letra = '1';
    idx = 1;
}

void TypeLetter(char L) {
    ura *atras;
    atras = movimientos[idx - 1];
    if(atras->letra == '0'){
        atras = atras->ancestros[0];
    }
    movimientos[idx] = new ura();
    movimientos[idx]->letra = L;
    movimientos[idx]->longitud = atras->longitud + 1;
    movimientos[idx]->ancestros[0] = atras;
    forn(i, 1, log2maxn){
        if(atras->ancestros[i - 1] == nullptr){
            break;
        }
        movimientos[idx]->ancestros[i] = atras->ancestros[i - 1];
        atras = atras->ancestros[i - 1];
    }
    idx ++;
}

void UndoCommands(int U) {
    ura *atras = movimientos[idx - U - 1];
    movimientos[idx] = new ura();
    if(atras->letra == '0'){
        atras = atras->ancestros[0];
    }
    movimientos[idx]->ancestros[0] = atras;
    idx ++;
}

char GetLetter(int P) {
    ura *actual = movimientos[idx - 1];
    if(actual->letra == '0'){
        actual = actual->ancestros[0];
    }
    P = actual->longitud - P;
    P --;
    fora(i, log2maxn, 0){
        if((P & (1 << i))){
            actual = actual->ancestros[i];
        }
    }
    return actual->letra;
}

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