Submission #516116

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

scrivener

#include <bits/stdc++.h>

using namespace std;

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

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

  }

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

  int query(int p) {
    assert(lastChar != '#');
    if (p == len - 1) {
      return lastChar;
    } else {
      return father->query(p);
    }
  }
};

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

  void undoHistory(int t) {
    int version = (int) history.size() - 1 - t;
    assert(0 <= version && version < (int) history.size());

    history.push_back(history[version]);
  }

  void addChar(char ch) {
   // cout << "start\n";
    history.push_back(history.back()->addChar(ch));
   // cout << "end\n";
  }

  int query(int p) {
   // cout << "L\n";
    int S = history.back()->query(p);
   // cout << "R\n";
    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:9:7: warning: 'Vertex::len' will be initialized after [-Wreorder]
    9 |   int len;
      |       ^~~
scrivener.cpp:8:11: warning:   'Vertex* Vertex::father' [-Wreorder]
    8 |   Vertex* father;
      |           ^~~~~~
scrivener.cpp:13:3: warning:   when initialized here [-Wreorder]
   13 |   Vertex() :
      |   ^~~~~~

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