Submission #255416

#	Time	Username	Problem	Language	Result	Execution time	Memory
255416		ChrisT	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	704 ms	165472 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
vector<int> ans;
int trie[1000001][26], depth[1000001], p[1000001][21], inc;
char letter[1000001];
void Init(){
  inc = 0;
  memset(p,-1,sizeof p);
  ans.push_back(0);
}
void TypeLetter(char L){
  int cur = ans[ans.size()-1], ch = L-'a';
  if (!trie[cur][ch]) {
    trie[cur][ch] = ++inc;
    depth[inc] = depth[cur] + 1;
    p[inc][0] = cur;
    for (int x = 1; x <= LOG; x++)
      if (~p[inc][x-1])
        p[inc][x] = p[p[inc][x-1]][x-1];
    letter[inc] = L;
  }
  ans.push_back(trie[cur][ch]);
}
void UndoCommands(int U){
  ans.push_back(ans[ans.size()-1-U]);
}
char GetLetter(int P){
  int cur = ans.back(); P++;
  for (int x = LOG; x >= 0; x--)
    if (~p[cur][x] && depth[p[cur][x]] >= P)
      cur = p[cur][x];
  return letter[cur];
}

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