Submission #404482

#	Time	Username	Problem	Language	Result	Execution time	Memory
404482		radaiosm7	Crayfish scrivener (IOI12_scrivener)	C++98	100 / 100	603 ms	169248 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
int currNode, p, i, query;
vector<int> commands;
int up[1000005][21];

typedef struct node {
  int children[26];
  char letter;
  int dep;

  node() {
    fill(children, children+26, -1);
  };
} node;

vector<node> trie;

void Init() {
  currNode = 0;
  trie.emplace_back();
  trie[0].letter = 'a';
  trie[0].dep = -1;
  commands.push_back(0);
  for (i=0; i < 21; ++i) {
    up[0][i] = 0;
  }
}

void TypeLetter(char L) {
  p = currNode;
  if (trie[currNode].children[L-'a'] == -1) {
    trie[currNode].children[L-'a'] = trie.size();
    trie.emplace_back();
  }
  currNode = trie[currNode].children[L-'a'];
  trie[currNode].letter = L;

  up[currNode][0] = p;
  trie[currNode].dep = trie[p].dep+1;
  for (i=1; i < 21; ++i) {
    up[currNode][i] = up[up[currNode][i-1]][i-1];
  }
  commands.push_back(currNode);
}

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

char GetLetter(int P) {
  P = trie[currNode].dep-P;
  query = currNode;
  for (i=0; i < 21 && P > 0; ++i) {
    if (P & 1) {
      query = up[query][i];
    }
    P >>= 1;
  }
  return trie[query].letter;
}

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