제출 #1199387

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199387		SonicML	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	546 ms	93356 KiB

scrivener

#include <vector>

struct Edge{
  int from;
  char ch;
};

int allnode = 0;

int const NMAX = 1e6; 
int jump[21][1 + NMAX];
int siz[1 + NMAX];
Edge parent[1 + NMAX];

void buildJump(int node) {
  jump[0][node] = parent[node].from;
  for(int k = 1;k <= 20;k++) { 
    jump[k][node] = jump[k-1][jump[k-1][node]];
  } 
}

void Init() {
  // WARIOWARE !!!
}

void TypeLetter(char L) {
  allnode++;
  parent[allnode] = {allnode-1, L};
  siz[allnode] = siz[allnode-1] + 1;
  buildJump(allnode);
}

void UndoCommands(int U) {
  int from = allnode - U;
  allnode++;
  parent[allnode] = {from, 0};
  siz[allnode] = siz[from];
  buildJump(allnode);
}

int cautbin(int node, int len) {
  for(int k = 20;k >= 0;k--) {
    int temp = jump[k][node];
    if(siz[temp] >= len) {
      node = temp;
    }
  }
  return node;
}

char GetLetter(int P) {
  int tempNode = cautbin(allnode, P+1);   
  return parent[tempNode].ch;
}

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