Submission #1000396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000396		blue	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	507 ms	88400 KiB

scrivener

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

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