Submission #350366

#	Time	Username	Problem	Language	Result	Execution time	Memory
350366		casperwang	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	643 ms	95604 KiB

scrivener

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define debug(args) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int L = 20;
struct node {
  int len;
  char c;
  int pos, anc[L];
  node(int id) {
    len = 0, pos = 0;
    for (int i = 0; i < L; i++)
      anc[i] = id;
  }
  node() {}
};
vector <node> arr;

void Init() {
  arr.pb(node(0));
}

void TypeLetter(char C) {
  int sze = arr.size();
  node now;
  now.len = arr[sze-1].len + 1;
  now.c = C;
  now.pos = sze;
  now.anc[0] = arr[sze-1].pos;
  for (int i = 1; i < L; i++) {
    now.anc[i] = arr[now.anc[i-1]].anc[i-1];
  }
  arr.pb(now);
}

void UndoCommands(int U) {
  int sze = arr.size();
  node now = arr[sze-1-U];
  arr.pb(now);
}

char GetLetter(int P) {
  int pos = arr[arr.size()-1].pos;
  int jump = arr[pos].len - P - 1;
  for (int i = 0; i < L; i++) {
    if (jump & (1<<i)) {
      pos = arr[pos].anc[i];
    }
  }
  return arr[pos].c;
}

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