제출 #107591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107591		MrTEK	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	34 / 100	1053 ms	79896 KiB

scrivener

const int N = 1e6 + 5;
const int LOG = 21;
int cnt,back[N][LOG + 1],sz[N];
char ch[N];

void Init() {

}

void TypeLetter(char L) {
  cnt++;
  back[cnt][0] = cnt - 1;
  for (int i = 1 ; i <= LOG ; i++)
    back[cnt][i] = back[back[cnt][i - 1]][i - 1];
  sz[cnt] = sz[cnt - 1] + 1;
  ch[cnt] = L;
}

void UndoCommands(int U) {
  cnt++;
  back[cnt][0] = cnt - U - 1;
  for (int i = 1 ; i <= LOG ; i++)
    back[cnt][i] = back[back[cnt][i - 1]][i - 1];
  sz[cnt] = sz[cnt - U - 1];
  ch[cnt] = ch[cnt - U - 1];  
}

char GetLetter(int P) {
  P++;
  int x = cnt;
  for (int i = LOG ; i >= 0 ; i--)
    if (sz[back[x][i]] >= P)
      x = back[x][i];
  return ch[x];
}

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