Submission #409641

#	Time	Username	Problem	Language	Result	Execution time	Memory
409641		pliam	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	414 ms	151624 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
#define MAXL 25//max logN

int up[MAXL][MAXN];
vector<int> ver_node;
int trie[MAXN][26];
char let[MAXN];//letter
int len[MAXN];//length of word
int max_node;

void Init() {
  ver_node.push_back(0);//fake root
}

void TypeLetter(char L) {
  int curr=ver_node.back();
  if(trie[curr][L-'a']==0){
    max_node++;
    trie[curr][L-'a']=max_node;
    ver_node.push_back(max_node);
    let[max_node]=L;
    len[max_node]=len[curr]+1;
    up[0][max_node]=curr;
    for(int i=1;i<MAXL;i++){
      up[i][max_node]=up[i-1][up[i-1][max_node]];
    }
  }else{
    ver_node.push_back(trie[curr][L-'a']);
  }
}

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

char GetLetter(int P) {
  int curr=ver_node.back();
  int num=len[curr]-P-1;
  for(int i=0;i<MAXL;i++,num>>=1){
    if(num&1){
      curr=up[i][curr];
    }
  }
  return let[curr];
}

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