Submission #652761

#	Time	Username	Problem	Language	Result	Execution time	Memory
652761		alvinpiter	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	803 ms	153424 KiB

scrivener

/*
* Build a trie. Everytime TypeLetter is called, add a child to the current node. The path from the root to the
  current node will be our current string.
* To handle GetLetter fast, we need to use binary jumping technique.
* To handle UndoCommands, we need another data structure to know where we are at the trie after executing the first k
  commands. This is simple, just use a vector.
*/

#include<bits/stdc++.h>
using namespace std;
#define MAXLG 20

struct Node {
  int depth;
  char ch;
  Node* ancestors[MAXLG + 3];

  Node(int depth_, char ch_, Node* parent = NULL) {
    depth = depth_;
    ch = ch_;
    for (int lg = 0; lg <= MAXLG; lg++) {
      ancestors[lg] = (parent == NULL ? NULL : parent->getKthParent((1 << lg) - 1));
    }
  }

  Node* getKthParent(int k) {
    Node* current = this;
    for (int lg = 0; lg <= MAXLG && current != NULL; lg++) {
      if (k & (1 << lg)) {
        current = current->ancestors[lg];
      }
    }

    return current;
  }
};

Node* root = new Node(0, '.');
Node* currentNode = root;

vector<Node*> positions;

void Init() {
  positions.push_back(root);
}

void TypeLetter(char L) {
  Node* newNode = new Node(currentNode->depth + 1, L, currentNode);

  positions.push_back(newNode);
  currentNode = newNode;
}

void UndoCommands(int U) {
  Node* node = positions[positions.size() - 1 - U];

  positions.push_back(node);
  currentNode = node;
}

char GetLetter(int P) {
  return currentNode->getKthParent(currentNode->depth - 1 - P)->ch;
}

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