Submission #590018

#	Time	Username	Problem	Language	Result	Execution time	Memory
590018		aci	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	696 ms	147424 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define N 1000009
#define l 25

struct val
{
    char c;
    int ref, dist;
};

int pos = 0;

vector<vector<int>> anc(N, vector<int> (l));
vector<val> v(N);

void Init() 
{
    v[0] = {'$', 0, 0};
    for(int i=0; i<l; i++) anc[0][i] = 0;
}

void TypeLetter(char L) 
{

  val last = v[pos];
  v[pos+1] = {L, pos, last.dist+1};
  pos++;
  anc[pos][0] = v[pos].ref;
  for(int i=1; i<l; i++) anc[pos][i] = anc[anc[pos][i-1]][i-1];

}

void UndoCommands(int U) 
{
    int par = pos-U;
    val x = v[par];
    pos++;
    v[pos] = x;
    anc[pos] = anc[par];
}

char GetLetter(int P) {

    int livcurr = v[pos].dist;
    int steps = livcurr - P - 1;
    if(steps==0) return v[pos].c;

    int sol = pos;

    for(int i=0; i<l; i++) if( steps & (1<<i) ) sol = anc[sol][i];

    return v[sol].c;
}

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