Submission #766963

#	Time	Username	Problem	Language	Result	Execution time	Memory
766963		boris_mihov	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	283 ms	67428 KiB

scrivener

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

typedef long long llong;
const int MAXLOG = 20;
const int MAXN = 1000000 + 10;

int d[MAXN];
char value[MAXN];
struct Sparse
{
    int sparse[MAXLOG][MAXN];
    void pushNode(int node, int p)
    {
        d[node] = d[p] + 1;
        sparse[0][node] = p;
        for (int log = 1 ; log < MAXLOG ; ++log)
        {
            sparse[log][node] = sparse[log - 1][sparse[log - 1][node]];
        }
    }

    int findKth(int node, int k)
    {
        for (int i = MAXLOG - 1 ; i >= 0 ; --i)
        {
            if (k & (1 << i))
            {
                node = sparse[i][node];
            }
        }

        return node;
    }
};

int cnt;
Sparse sparse;
std::vector <int> atMoment;

void Init()
{
    atMoment.push_back(0);
}

void TypeLetter(char L) 
{
    cnt++;
    value[cnt] = L;
    sparse.pushNode(cnt, atMoment.back());
    atMoment.push_back(cnt);
}

void UndoCommands(int U)
{
    atMoment.push_back(atMoment[atMoment.size() - 1 - U]);
}

char GetLetter(int P)
{
    return value[sparse.findKth(atMoment.back(), d[atMoment.back()] - P - 1)];
}

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