Submission #103002

#	Time	Username	Problem	Language	Result	Execution time	Memory
103002		wxh010910	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	834 ms	90668 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int N = 1234567;
const int LOG = 20;

int t, from[N], depth[N], anc[N][LOG];
char type[N];

void Init() {
  t = 1;
}

void TypeLetter(char L) {
  type[t] = L;
  depth[t] = depth[from[t - 1]] + 1;
  anc[t][0] = from[t - 1];
  for (int i = 1; depth[t] >> i; ++i) {
    anc[t][i] = anc[anc[t][i - 1]][i - 1];
  }
  from[t] = t;
  ++t;
}

void UndoCommands(int U) {
  from[t] = from[t - 1 - U];
  ++t;
}

char GetLetter(int P) {
  int jump = depth[from[t - 1]] - 1 - P;
  int x = from[t - 1];
  for (int i = 0; jump >> i; ++i) {
    if (jump >> i & 1) {
      x = anc[x][i];
    }
  }
  return type[x];
}

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