Submission #589980

#	Time	Username	Problem	Language	Result	Execution time	Memory
589980		aci	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1076 ms	131980 KiB

scrivener

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

int l;

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

vector<vector<int>> anc;
vector<val> v;

void Init() 
{
    v.push_back({'$', 0, 0});
    l = 21;
    anc.resize(N, vector<int> (l));
    for(int i=0; i<l; i++) anc[0][i] = 0;
}

void TypeLetter(char L) 
{

  val last = v[v.size()-1];
  v.push_back({L, int(v.size())-1, last.dist+1});
  int pos = v.size()-1;
  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[v.size()-1-U];
    v.push_back(x);
    int pos = v.size()-1;
    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 = v.size()-1;
    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