Submission #1000397

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000397		blue	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	425 ms	82884 KiB

scrivener

#include <vector>
#include <iostream>
using namespace std;
 
int curr;
int len[1000001];
char last[1000001];
int letter_anc[1000001][20];
 
void Init()
{
    curr = 0;
 
    len[0] = -1;
    last[0] = '?';
    for(int e = 0; e < 20; e++)
        letter_anc[0][e] = 0;
}
 
void TypeLetter(char L)
{
    curr++;
    len[curr] = len[curr-1] + 1;
    last[curr] = L;
 
    letter_anc[curr][0] = curr-1;
    for(int e = 1; e < 20; e++)
    {
        letter_anc[curr][e] = letter_anc[ letter_anc[curr][e-1] ][e-1];
    }
 
    // cerr << curr << '\n';
}
 
void UndoCommands(int U)
{
    int prev = curr - U;
 
    // cerr << "making copy of " << prev << '\n';
 
    curr++;
    len[curr] = len[prev];
    last[curr] = last[prev];
 
    letter_anc[curr][0] = letter_anc[prev][0];
 
    for(int e = 1; e < 20; e++)
    {
        letter_anc[curr][e] = letter_anc[ letter_anc[curr][e-1] ][e-1];
    }
 
    // cerr << curr << '\n';
}
 
char GetLetter(int P)
{
    int pos = curr;
    for(int e = 19; e >= 0; e--)
        if(len[ letter_anc[pos][e] ] >= P)
            pos = letter_anc[pos][e];
 
    return last[pos];
}

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