Submission #546287

#	Time	Username	Problem	Language	Result	Execution time	Memory
546287		Jomnoi	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	429 ms	89564 KiB

scrivener

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

const int N = 1e6 + 10;

int now = 0;

class Crayfish {
public :
    char letter;
    int len;
    int par[20];
}s[N];

void Init() {}

void TypeLetter(char L) {
    now++;
    s[now] = s[now - 1];
    s[now].letter = L;
    s[now].len = s[now - 1].len + 1;
    s[now].par[0] = now - 1;
    for(int i = 1; i < 20; i++) {
        s[now].par[i] = s[s[now].par[i - 1]].par[i - 1];
    }
}

void UndoCommands(int U) {
    now++;
    s[now] = s[now - U - 1];
}

char GetLetter(int P) {
    P = s[now].len - P - 1;
    int res = now;
    for(int i = 0; i < 20; i++) {
        if(P & (1<<i)) {
            res = s[res].par[i];
        }
    }
    return s[res].letter;
}

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