Submission #130660

#	Time	Username	Problem	Language	Result	Execution time	Memory
130660		dragonslayerit	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	715 ms	93944 KiB

scrivener

#include <string>

struct String{
  int len;
  char last;
  int prev[20];
  String():len(0),last('\0'){
  }
}str[1000001];
int curr=0;


void Init() {}

void TypeLetter(char L) {
  str[curr+1].len=str[curr].len+1;
  str[curr+1].last=L;
  str[curr+1].prev[0]=curr;
  for(int k=1;k<20;k++){
    str[curr+1].prev[k]=str[str[curr+1].prev[k-1]].prev[k-1];
  }
  curr++;
}

void UndoCommands(int U) {
  str[curr+1]=str[curr-U];
  curr++;
}

char GetLetter(int P) {
  int move=str[curr].len-1-P;
  int x=curr;
  for(int k=0;k<20;k++){
    if(move&(1<<k)){
      x=str[x].prev[k];
    }
  }
  return str[x].last;
}

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