Submission #118497

#	Time	Username	Problem	Language	Result	Execution time	Memory
118497		win11905	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	787 ms	63504 KiB

scrivener

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

const int N = 1e6+1;

int step, ptr;
int par[N][20];
char val[N];
int sz[N], pos[N];

void Init() { }

void TypeLetter(char L) {
  val[++ptr] = L;
  par[ptr][0] = pos[step];
  sz[step+1] = sz[step];
  for(int i = 1; i < 20; ++i) par[ptr][i] = par[par[ptr][i-1]][i-1];
  sz[++step]++;
  pos[step] = ptr;
}

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

char GetLetter(int P) {
  int jump = sz[step] - P - 1;
  int p = pos[step];
  for(int i = 19; ~i; --i) if(jump >> i & 1) p = par[p][i];
  return val[p];
}

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