Submission #1183898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183898		peteza	Crayfish scrivener (IOI12_scrivener)	C++20	74 / 100	780 ms	274276 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

struct node {
  node *par[22] = {};
  node *child[26] = {};
  int dep = 0;
  node() {}

} *roots[1000005];

int cround = 0;

void Init() {
  roots[0] = new node();
  cround = 0;
}

void TypeLetter(char L) {
  L -= 'a';
  if(roots[cround]->child[L]) {roots[cround+1] = roots[cround]->child[L];}
  else {
    roots[cround]->child[L] = new node();
    roots[cround]->child[L]->par[0] = roots[cround];
    for(int i=0;i<21;i++) {
      if(roots[cround]->child[L]->par[i]->par[i]) {
        roots[cround]->child[L]->par[i+1] = roots[cround]->child[L]->par[i]->par[i];
      } else break;
    }
    roots[cround]->child[L]->dep = roots[cround]->dep + 1;
    roots[cround+1] = roots[cround]->child[L];
  }
  cround++;
}

void UndoCommands(int U) {
  roots[cround+1] = roots[cround - U];
  cround++;
}

node *getpar(node * cur, int res) {
  if(!res) return cur;
  if(res > cur->dep) exit(1);
  for(int i=20;i>=0;i--) if((1 << i) & res) cur = cur->par[i];
  return cur;
}

char GetLetter(int P) {
  auto olderpar = getpar(roots[cround], roots[cround]->dep - P), newerpar = getpar(roots[cround], roots[cround]->dep-P-1);
  for(int i=0;i<26;i++) {
    if(olderpar->child[i] == newerpar) {
      return i+'a';
    }
  }
  exit(1);
}

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