Submission #753157

#	Time	Username	Problem	Language	Result	Execution time	Memory
753157		nicksms	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	520 ms	144476 KiB

scrivener

/**
 *      Author:  Nicholas Winschel
 *      Created: 06.04.2023 10:21:03
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

struct node {
  int h=0; char c='.';
  array<node *, 22> jmp;

  node () {
    for (int i = 0; i < 22; i++) {
      jmp[i]=this;
    }
  }

  node (node *par, char _c) : c(_c) {
    jmp[0]=par;
    // cerr << "dbg: " << jmp[0]->c << endl;
    // cerr << "0\n";
    // cerr << jmp[0] << "\n";
    h=par->h + 1;
    for (int i = 1; i < 22; i++) {
      // cerr << i << endl;
      jmp[i]=jmp[i-1]->jmp[i-1];
      // cout << jmp[i] << endl;
      // cerr << jmp[i]->c << endl; 
    }
  }

  char get(int p) {
    int ab = h-p-1;
    node *cur = this;
    for (int i = 0; i < 22; i++) if (ab&(1<<i)) cur = cur->jmp[i];
    return cur->c;
  }

};

V<node*> roots;
char last;

void Init() {
  roots.push_back(new node);
}

void TypeLetter(char L) {
  // cerr << "T " << L << " " << roots[sz(roots)-1]->c << endl;
  roots.push_back(new node(roots[sz(roots)-1], L));
}

void UndoCommands(int U) {
  // cerr << "U " << U << endl; 
  roots.push_back(roots[sz(roots)-1-U]);
}

char GetLetter(int P) {
  // cerr << "P " << P << endl;
  return roots[sz(roots)-1]->get(P);
}

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