Submission #1041378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041378		ArthuroWich	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	190 ms	142364 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
int st = 0, co = 1, a[1000005], depth[1000005], ch[1000005], trie[1000005][26], succ[1000005][20];
void Init() {};
void initsucc(int i) {
    for (int j = 1; j < 20; j++) {
        succ[i][j] = succ[succ[i][j-1]][j-1];
    }
}
int kthjump(int a, int k) {
    for (int i = 0; i < 20; i++) {
        if (k & (1 << i)) {
            a = succ[a][i];
        }
    }
    return a;
}
void TypeLetter(char l) {
    int n = a[st], c = l-'a';
    st++;
    if (!trie[n][c]) {
        succ[co][0] = n;
        depth[co] = depth[n]+1;
        trie[n][c] = co;
        ch[co] = c;
        initsucc(co);
        co++;
    }
    a[st] = trie[n][c];
}
void UndoCommands(int U) {
    st++;
    a[st] = a[st-1-U];
}
char GetLetter(int P) {
    int n = a[st];
    int a = kthjump(n, depth[n]-1-P);
    return (char)(ch[a]+'a');
}

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