Submission #315027

#	Time	Username	Problem	Language	Result	Execution time	Memory
315027		Ozy	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	434 ms	39544 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 jump;
};
 
 
lli p,act,cont = 1;
x instruccion[1000002];
lli salto[1000002];
 
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 = cont - 1;
 
    if (instruccion[cont].nivel > 1) {
      if (instruccion[p].jump > 0 && instruccion[instruccion[cont].padre].jump == instruccion[salto[instruccion[cont].padre]].jump) {
          salto[cont] = salto[salto[instruccion[cont].padre]];
          instruccion[cont].jump = instruccion[instruccion[cont].padre].jump*2 + 1;
      }
      else {
          salto[cont] = instruccion[cont].padre;
          instruccion[cont].jump = 1;
      }
    }
 
    cont++;
}
 
void UndoCommands(int U) {
    instruccion[cont] = instruccion[cont - U - 1];
    act = 0;
    salto[cont] = salto[cont - U - 1];
 
    cont++;
}
 
char GetLetter(int P) {
 
    act = cont-1;
    p = instruccion[act].nivel;
    P++;
 
    while (P < p) {
        if (p - instruccion[act].jump >= P) {
            p -= instruccion[act].jump;
            act = salto[act];
        }
        else {
            p--;
            act = instruccion[act].padre;
        }
    }
 
    return instruccion[act].letra;
}

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