Submission #120757

#	Time	Username	Problem	Language	Result	Execution time	Memory
120757		MAMBA	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	872 ms	172280 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

#define rep(i, j, k) for (int i = j; i < int(k); i++)

constexpr int N = 1e6 + 10;

struct node {
  node* par[20];
  char c = '\0';
  int deep = -1;
  node() { fill(par, par + 20, this); }
  node(char c_, node* p) {
    par[0] = p, c = c_;
    deep = p->deep + 1;
    rep(i, 1, 20) par[i] = par[i - 1]->par[i - 1];
  }
} state[N];

int now;
void Init() { now = 0; }

void TypeLetter(char L) {
  now++;
  state[now] = node(L, &state[now - 1]);
}

void UndoCommands(int U) {
  now++;
  state[now] = state[now - U - 1];
}

char GetLetter(int P) {
  int goUp = state[now].deep - P;
  node* me = &state[now];
  rep(i, 0, 20) if (goUp >> i & 1) me = me->par[i];
  return me->c;
}

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