Submission #1021173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021173		aufan	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	294 ms	94420 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

void Init() {}

int p[1111111][22], sz[1111111], id = 0;
char c[1111111];

void TypeLetter(char l) {
  id += 1;
  c[id] = l;
  p[id][0] = id - 1;
  sz[id] = sz[id - 1] + 1;
  for (int i = 1; i < 20; i++) {
    p[id][i] = p[p[id][i - 1]][i - 1];
  }
}

void UndoCommands(int u) {
  id += 1;
  c[id] = c[id - u - 1];
  sz[id] = sz[id - u - 1];
  for (int i = 0; i < 20; i++) {
    p[id][i] = p[id - u - 1][i];
  }
}

char GetLetter(int x) {
  int d = sz[id] - (x + 1), cur = id;
  for (int i = 0; i < 20; i++) {
    if (d >> i & 1) {
      cur = p[cur][i];
    }
  }

  return c[cur];
}

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