Submission #483238

#	Time	Username	Problem	Language	Result	Execution time	Memory
483238		syl123456	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	942 ms	185020 KiB

scrivener

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

vector<char> c;
vector<int> dep, ptr;
vector<vector<int>> pa, ch;

void Init() {
  c.push_back('.');
  dep.push_back(0);
  ptr.push_back(0);
  pa.emplace_back(20, 0);
  ch.emplace_back(26, -1);
}

void TypeLetter(char L) {
  int y = L - 'a', x = ptr.back();
  if (ch[x][y] == -1) {
    int i = ch[x][y] = c.size();
    c.push_back(L);
    dep.push_back(dep[x] + 1);
    pa.emplace_back(20);
    ch.emplace_back(26, -1);
    pa[i][0] = x;
    for (int j = 1; j < 20; ++j)
      pa[i][j] = pa[pa[i][j - 1]][j - 1];
  }
  ptr.push_back(ch[x][y]);
}

void UndoCommands(int U) {
  int i = ptr.size() - 1 - U;
  ptr.push_back(ptr[i]);
}

char GetLetter(int P) {
  ++P;
  int i = ptr.back();
  for (int j = 19; ~j; --j)
    if (dep[pa[i][j]] >= P)
      i = pa[i][j];
  return c[i];
}

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