Submission #577655

#	Time	Username	Problem	Language	Result	Execution time	Memory
577655		AngusWong	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	592 ms	162452 KiB

scrivener

#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;

const int N=1e6+1;
int cur, up[N][21];
vector<char> trie;
vector<vector<int> > nxt;
vector<int> len, step;

void Init() {
    cur=0;
    trie.clear();
    nxt.clear();
    len.clear();
    trie.push_back('!');
    nxt.push_back(vector<int>(26, -1));
    len.push_back(0);
    for (int i=0; i<=20; i++) up[0][i]=-1;
    step.clear();
    step.push_back(cur);
}

void TypeLetter(char L) {
    if (nxt[cur][L-'a']==-1){
        trie.push_back(L);
        nxt.push_back(vector<int>(26, -1));
        nxt[cur][L-'a']=trie.size()-1;
        len.push_back(len[cur]+1);
        up[trie.size()-1][0]=cur;
        for (int i=1; i<=20; i++){
            up[trie.size()-1][i]=(up[trie.size()-1][i-1]==-1? -1: up[up[trie.size()-1][i-1]][i-1]);
        }
    }
    cur=nxt[cur][L-'a'];
    step.push_back(cur);
}

void UndoCommands(int U) {
    cur=step[step.size()-U-1];
    step.push_back(cur);
}

char GetLetter(int P) {
    P=len[cur]-P-1;
    int t=cur;
    for (int i=20; i>=0; i--){
        if (P>=(1<<i)){
            P-=(1<<i);
            t=up[t][i];
        }
    }
    return trie[t];
}

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