Submission #783108

#	Time	Username	Problem	Language	Result	Execution time	Memory
783108		radaiosm7	Crayfish scrivener (IOI12_scrivener)	C++98	100 / 100	631 ms	106028 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
int up[1000005][24];
int dep[1000005];
char cr[1000005];
int pos[1000005];
int curr, i, n;

void Init() {
  n = 0;
  pos[0] = 0;
  dep[0] = -1;
  for (i=0; i < 24; ++i) up[0][i] = 0;
}

void TypeLetter(char L) {
  ++n;
  pos[n] = n;
  cr[n] = L;
  dep[n] = dep[pos[n-1]]+1;
  up[n][0] = pos[n-1];
  for (i=1; i < 24; ++i) up[n][i] = up[up[n][i-1]][i-1];
}

void UndoCommands(int U) {
  ++n;
  pos[n] = pos[n-1-U];
}

char GetLetter(int P) {
  curr = pos[n];
  for (i=23; i >= 0; --i) if (dep[up[curr][i]] >= P) curr = up[curr][i];
  return cr[curr];
}

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