Submission #767962

#	Time	Username	Problem	Language	Result	Execution time	Memory
767962		raysh07	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	553 ms	86712 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

int timer;
const int N = 1e6 + 2;
int lift[20][N], len[N];
char last[N];

void Init() {
    timer = 0;
}

void TypeLetter(char l) {
    timer++;
    lift[0][timer] = timer - 1;
    for (int i = 1; i < 20; i++){
        lift[i][timer] = lift[i - 1][lift[i - 1][timer]];
    }
    last[timer] = l;
    len[timer] = len[timer - 1] + 1;
}

void UndoCommands(int u) {
    int ok = timer - u;
    timer++;
    
    len[timer] = len[ok];
    last[timer] = last[ok];
    for (int i = 0; i < 20; i++) lift[i][timer] = lift[i][ok];
}

char GetLetter(int p) {
    p++;
    int ok = timer;
    for (int i = 19; i >= 0; i--){
        int x = lift[i][ok];
        
        if (len[x] < p) continue;
        ok = x;
    }
    
    return last[ok];
}

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