Submission #1197875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197875		belgianbot	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	293 ms	90596 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
const int N = 1000000;
int p[N], depth[N], to[N];
int up[N][LOG];
char letter[N];
int cnt, last;

void create(int x) {

  up[x][0] = p[x];

  for (int i = 1; i < LOG; i++) {
    up[x][i] = up[up[x][i-1]][i-1];
  }
}
void Init() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cnt = 0;
  last = 0;
  depth[0] = -1;
}

void TypeLetter(char L) {
  to[cnt] = cnt;
  p[cnt] = last;
  depth[cnt] = depth[last] + 1;
  create(cnt);
  letter[cnt] = L;
  last = cnt;
  cnt++;
}

void UndoCommands(int U) {
  to[cnt] = to[cnt - U - 1];
  last = to[cnt];
  cnt++;
}

char GetLetter(int P) {
  int distance = depth[last] - P, x = last;
  for (int i = LOG; i >= 0; i--) {
    if (distance & (1<<i)) x = up[x][i];
  }
  return letter[x];
}

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