Submission #70773

#	Time	Username	Problem	Language	Result	Execution time	Memory
70773		doowey	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1092 ms	137260 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

char last;
const int LOG = 22;
const int N = (int)1e6 + 50;

struct Trie{
	char value;
  Trie *nex[22];
  int siz;
  Trie(){
    value = '!';
    for(int i = 0; i < 22;i ++ ){
      nex[i] = NULL;
    }
    siz = 0;
  }
};

Trie *Q[N];
int cnt;

void Init() {
	Q[0] = new Trie();
}

void TypeLetter(char L) {
  ++ cnt;
  Q[cnt] = new Trie();
  Q[cnt] -> nex[0] = Q[cnt - 1];
  for(int i = 1; i < LOG; i ++ ){
    if(Q[cnt] -> nex[i - 1] != NULL){
      Q[cnt] -> nex[i] = Q[cnt] -> nex[i - 1] -> nex[i - 1];
    } 
  }
  Q[cnt] -> value = L;
  Q[cnt] -> siz = Q[cnt] -> nex[0] -> siz + 1;
}

void UndoCommands(int U) {
  ++ cnt;
  Q[cnt] = Q[cnt - U - 1];
}

char GetLetter(int P) {
  int dep = Q[cnt] -> siz;
  dep = dep - 1 - P;
  Trie *T = Q[cnt];
  for(int i = 0;i < LOG;i ++ ){
    if(dep & (1 << i)){
      T = T -> nex[i];
    }
  }
  return T -> value;
}

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