Submission #370695

#	Time	Username	Problem	Language	Result	Execution time	Memory
370695		WLZ	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	930 ms	88056 KiB

scrivener

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

const int MAXN = (int) 1e6;
const int MAX_LOG = 20;
int sz = 0;
int up[MAXN][MAX_LOG + 1];
int len[MAXN];
char s[MAXN];

void Init() {}

void TypeLetter(char L) {
  s[sz] = L;
  len[sz] = 1;
  if (sz > 0) len[sz] += len[sz - 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[sz] = s[idx];
  len[sz] = len[idx];
  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: 26 / 26
• Subtask 5: 40 / 40