Submission #799114

#	Time	Username	Problem	Language	Result	Execution time	Memory
799114		I_Love_EliskaM_	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	610 ms	90476 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

const int K=21;
const int N=1e6+55;
int jump[N][K];
char z[N];
int dp[N];

void Init() {dp[0]=0;}
int op=0;
void TypeLetter(char c) {
  ++op;
  z[op]=c;
  jump[op][0]=op;
  dp[op]=dp[op-1]+1;
  jump[op][1]=jump[op-1][0];
  for (int i=2; i<K; ++i) {
    jump[op][i]=jump[jump[op][i-1]][i-1];
  }
}
void UndoCommands(int x) {
  ++op;
  dp[op]=dp[op-x-1];
  jump[op][0]=jump[op-x-1][0];
  jump[op][1]=jump[op-x-1][1];
  for (int i=2; i<K; ++i) {
    jump[op][i]=jump[jump[op][i-1]][i-1];
  }
}
char GetLetter(int p) {
  int n=dp[op];
  int u=jump[op][0];
  int x=n-1-p;
  for (int i=K-1; i>0; --i) {
    if (x&(1<<(i-1))); else continue;
    u=jump[u][i];
  }
  return z[u];
}

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