Submission #434358

#	Time	Username	Problem	Language	Result	Execution time	Memory
434358		kevinxiehk	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	936 ms	259392 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
int loc[1000005];
struct node{
    int dep;
    char curr;
    int up;
    int par[25];
    unordered_map<char, int> ch;
};
node trie[1000005];
int cnt = 1;
int step = 0;
void Init() {
    loc[0] = 0;
    for(int i = 0; i < 1000000; i++) for(int j = 0; j < 25; j++) trie[i].par[j] = i;
    return;
}

void TypeLetter(char L) {
    step++;
    int lst = loc[step - 1];
    if(trie[lst].ch[L] == 0) {
        trie[lst].ch[L] = cnt;
        trie[cnt].dep = trie[lst].dep + 1;
        trie[cnt].curr = L;
        trie[cnt].par[0] = lst;
        for(int i = 1; i < 25; i++) {
            trie[cnt].par[i] = trie[trie[cnt].par[i - 1]].par[i - 1];
        }
        cnt++;
    }
    loc[step] = trie[lst].ch[L];
}

void UndoCommands(int U) {
    step++;
    loc[step] = loc[step - U - 1];
}

char GetLetter(int p) {
    p++;
    int dif = trie[loc[step]].dep - p;
    int pt = loc[step], hm = 0;
    while(dif) {
        if(dif & (1 << hm)) {
            pt = trie[pt].par[hm];
            dif -= (1 << hm);
        }
        hm++;
    }
    return trie[pt].curr;
}

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