Submission #857885

#	Time	Username	Problem	Language	Result	Execution time	Memory
857885		sleepntsheep	Crayfish scrivener (IOI12_scrivener)	C++17	12 / 100	452 ms	93356 KiB

scrivener

#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define ALL(x) x.begin(), x.end()

int p[20][1<<20], a[1<<20], ptr, dep[1<<20];
vector<int> chain;

void Init()
{
}

void TypeLetter(char l)
{
    a[1+ptr] = l; p[0][1+ptr] = ptr; dep[1+ptr] = dep[ptr]+1;
    for (int j = 1; j < 20; ++j) p[j][1+ptr] = p[j-1][p[j-1][1+ptr]];
    chain.push_back(++ptr); a[ptr] = l;
}

void UndoCommands(int u)
{
    ptr=chain[max((int)chain.size()-u-1, 0)]; chain.push_back(ptr);
}

char GetLetter(int k)
{
    int c = ptr; k = dep[c] - k-1;
    for (int j = 20; j--;) if (k & (1 << j)) c = p[j][c];
    return a[c];
}

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