Submission #589999

#	Time	Username	Problem	Language	Result	Execution time	Memory
589999		aci	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1082 ms	146792 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define N 1000009
#define l 25

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

int ultimo = 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[ultimo];
  v[ultimo+1] = {L, ultimo, last.dist+1};
  ultimo++;
  int pos = ultimo;
  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) 
{
    val x = v[ultimo-U];
    ultimo++;
    v[ultimo] = x;
    int pos = ultimo;
    anc[pos][0] = v[pos].ref;
    for(int i=1; i<l; i++) anc[pos][i] = anc[anc[pos][i-1]][i-1];
}

char GetLetter(int P) {

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

    int sol = curr;

    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: 0 / 26
• Subtask 5: 0 / 40