Submission #521502

#	Time	Username	Problem	Language	Result	Execution time	Memory
521502		Alex_tz307	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	406 ms	89484 KiB

scrivener

const int kN = 1e6;
const int kLog = 20;
int n;

struct node {
  char c;
  int len, p[kLog];
} a[1 + kN];

void Init() {

}

void TypeLetter(char L) {
  a[n + 1].c = L;
  a[n + 1].len = a[n].len + 1;
  a[n + 1].p[0] = n;
  n += 1;
  for (int i = 1; i < 20; ++i) {
    a[n].p[i] = a[a[n].p[i - 1]].p[i - 1];
    if (a[n].p[i] == 0) {
      break;
    }
  }
}

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

char GetLetter(int P) {
  int diff = a[n].len - P - 1;
  int curr = n;
  for (int i = 0; (1 << i) <= diff; ++i) {
    if (diff & (1 << i)) {
      curr = a[curr].p[i];
    }
  }
  return a[curr].c;
}

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