Submission #258798

#	Time	Username	Problem	Language	Result	Execution time	Memory
258798		SamAnd	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	635 ms	67424 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 1000006, m = 20;

int z;
char a[N];
int p[N][m];
int d[N];

vector<int> v;

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

void TypeLetter(char L)
{
    ++z;
    a[z] = L;
    p[z][0] = v.back();
    d[z] = d[v.back()] + 1;
    for (int i = 1; i < m; ++i)
        p[z][i] = p[p[z][i - 1]][i - 1];
    v.push_back(z);
}

void UndoCommands(int U)
{
    v.push_back(v[sz(v) - U - 1]);
}

char GetLetter(int P)
{
    ++P;
    int x = v.back();
    for (int i = m - 1; i >= 0; --i)
    {
        if (d[p[x][i]] >= P)
            x = p[x][i];
    }
    return a[x];
}

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