Submission #370687

#	Time	Username	Problem	Language	Result	Execution time	Memory
370687		WLZ	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1093 ms	107588 KiB

scrivener

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

int sz = 0, max_log = 21;
vector<int> len;
vector< vector<int> > up;
string s;

void Init() {}

void TypeLetter(char L) {
  s.push_back(L);
  if (len.empty()) len.push_back(1);
  else len.push_back(len.back() + 1);
  up.push_back(vector<int>(max_log + 1));
  if (sz == 0) up[0][0] = 0;
  else up[sz][0] = sz - 1;
  for (int i = 1; i <= max_log; i++) up[sz][i] = up[up[sz][i - 1]][i - 1];
  sz++;
}

void UndoCommands(int U) {
  int idx = sz - U - 1;
  s.push_back(s[idx]);
  len.push_back(len[idx]);
  up.push_back(vector<int>(max_log + 1));
  up[sz][0] = up[idx][0];
  for (int i = 1; i <= max_log; i++) up[sz][i] = up[up[sz][i - 1]][i - 1];
  sz++;
}

char GetLetter(int P) {
  P = len[sz - 1] - P - 1;
  int cur = sz - 1;
  for (int i = 0; i <= max_log; i++) if (P & (1 << i)) cur = up[cur][i];
  return s[cur];
}

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