Submission #516125

#	Time	Username	Problem	Language	Result	Execution time	Memory
516125		600Mihnea	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1101 ms	167768 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int C = 17;

class Vertex {
private:
  Vertex* kids[26];
  Vertex* father;
  Vertex* highway[C];
  int len;
  char lastChar;

public:
  Vertex() :
    len(0),
    father(nullptr),
    lastChar('#') {
    for (int i = 0; i < 26; i++) kids[i] = nullptr;
    for (int i = 0; i < C; i++) highway[i] = nullptr;
  }

  Vertex* addChar(char ch) {
    int id = ch - 'a';
    if (!kids[id]) {
      kids[id] = new Vertex;
      kids[id]->len = len + 1;
      kids[id]->father = this;
      kids[id]->lastChar = ch;
      for (int i = 0; i < C; i++) {
        int levels = (1 << i);
        if (0 <= levels && levels <= len) {
          kids[id]->highway[i] = getDown((1 << i) - 1);
        }
      }
    }
    return kids[id];
  }

  Vertex* getDown(int levels) {
    Vertex* current = this;
    for (int i = C - 1; i >= 0; i--) {
      while (levels >= (1 << i)) {
        current = current->highway[i];
        levels -= (1 << i);
      }
    }
    return current;
  }

  int query(int p) {
    Vertex* vertex = getDown(len - 1 - p);
    return vertex->lastChar;
  }
};

class VertexHandler {
private:
  vector<Vertex*> history;
public:
  VertexHandler() {
    history.push_back(new Vertex);
  }

  void undoHistory(int t) {
    int version = (int) history.size() - 1 - t;

    history.push_back(history[version]);
  }

  void addChar(char ch) {
    history.push_back(history.back()->addChar(ch));
  }

  int query(int p) {
    int S = history.back()->query(p);
    return S;
  }

} vertexHandler;

char last;

void Init() {}

void TypeLetter(char L) {
  vertexHandler.addChar(L);
  last = L;
}

void UndoCommands(int U) {
  vertexHandler.undoHistory(U);
}

char GetLetter(int P) {

  return vertexHandler.query(P);
}

Compilation message (stderr)

scrivener.cpp: In constructor 'Vertex::Vertex()':
scrivener.cpp:12:7: warning: 'Vertex::len' will be initialized after [-Wreorder]
   12 |   int len;
      |       ^~~
scrivener.cpp:10:11: warning:   'Vertex* Vertex::father' [-Wreorder]
   10 |   Vertex* father;
      |           ^~~~~~
scrivener.cpp:16:3: warning:   when initialized here [-Wreorder]
   16 |   Vertex() :
      |   ^~~~~~

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