Submission #38046

#	Time	Username	Problem	Language	Result	Execution time	Memory
38046		funcsr	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	666 ms	190628 KiB

scrivener

#include <iostream>
#include <vector>
#include <string>
#define rep(i, n) for (int i=0; i<(n); i++)
using namespace std;
int N;
int U[20][1000001];
char W[1000001];
int R[1000001];
int ch[1000001][26];

int alloc(int par, char c) {
  if (par != -1) R[N] = R[par]+1;
  W[N] = c;
  U[0][N] = par;
  for (int i=1; i<20; i++) U[i][N] = U[i-1][U[i-1][N]];
  return N++;
}

int next(int v, char c) {
  int k = c-'a';
  if (ch[v][k] == -1) ch[v][k] = alloc(v, c);
  return ch[v][k];
}

int cur = 0;
int V[1000000];

void Init() {
  rep(i, 1000000) rep(j, 26) ch[i][j] = -1;
  V[cur] = alloc(-1, '$');
}
void TypeLetter(char L) {
  V[cur+1] = next(V[cur], L);
  cur++;
}
void UndoCommands(int U) {
  V[cur+1] = V[cur-U];
  cur++;
}

inline int up(int v, int k) {
  for (int i=19; i>=0; i--) if ((k>>i)&1) v = U[i][v];
  return v;
}

char GetLetter(int P) {
  int v = V[cur];
  return W[up(v, R[v]-(P+1))];
}

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