Submission #652760

#	Time	Username	Problem	Language	Result	Execution time	Memory
652760		alvinpiter	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	808 ms	155516 KiB

scrivener

#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