Submission #1269173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269173		nerrrmin	Crayfish scrivener (IOI12_scrivener)	C++20	0 / 100	326 ms	58484 KiB

scrivener

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e6 + 10;
char last;
int n;
char onv[maxn];
int from[maxn], jump[maxn][22], len[maxn];
vector < int > g;
int curr;
void Init()
{
    n = 1;
    onv[1] = '-';
    len[1] = 0;
    curr = 1;
    g.pb(1);
}

void TypeLetter(char L) {

  last = L;
  n ++;

  from[n] = curr;
  onv[n] = L;
  len[n] = len[curr] + 1;
  jump[n][0] = curr;
  for (int j = 1; j < 21; ++ j)
  {
      jump[n][j] = jump[jump[n][j-1]][j-1];
  }
  curr = n;
    g.pb(curr);
}

void UndoCommands(int U)
{
    int sz = g.size()-1;
    curr = g[sz - U];
    g.pb(curr);
}

char GetLetter(int P)
{

    int state = curr;
    int on = state;
    int steps = len[curr] - P - 1;
    for (int bit = 0; bit < 21; ++ bit)
    {
        if((1 << bit) & steps)curr = jump[curr][bit];
    }
  return onv[curr];

}

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