Submission #1197854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197854		belgianbot	Crayfish scrivener (IOI12_scrivener)	C++20	0 / 100	132 ms	327680 KiB

scrivener

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

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];
    word[x][i] = word[x][i-1] + word[up[x][i-1]][i-1];
  }
}
char getWord(int x, int P) {
  int k = depth[x];
  string w;
  for (int i = LOG - 1; i >= 0; i--) {
    if (k & (1 << i)) {
      w += word[x][i];
      x = up[x][i];
    }
  }
  reverse(w.begin(), w.end());
  //cerr << w << '\n';
  return w[P];
}
void Init() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cnt = 0;
}

void TypeLetter(char L) {
  if (!cnt) {
    p[cnt] = 0;
    depth[cnt] = 1;
  }
  else {
    p[cnt] = cnt-1;
    depth[cnt] = depth[p[cnt]] + 1;
  }
  word[cnt][0] += L;
  create(cnt);
  cnt++;
}

void UndoCommands(int U) {
  p[cnt] = cnt - U - 1;
  depth[cnt] = depth[p[cnt]]+1;
  create(cnt);
  cnt++;
}

char GetLetter(int P) {
  return getWord(cnt-1, P);

}

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