Submission #481465

#	Time	Username	Problem	Language	Result	Execution time	Memory
481465		Haruto810198	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	797 ms	189264 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

struct Node{
    char val;
    int dep;
    vi nxt;
    vi anc;
    Node(char _val, int _dep): val(_val), dep(_dep), nxt(vi(26, 0)), anc(vi(20, 0)) {}
};

vector<Node> trie;
vi pos;
int ptr;

void Init(){
    trie.pb(Node('$', -1));
    pos.pb(0);
    ptr = 0;
}

void TypeLetter(char L){
    int& ch = trie[ptr].nxt[L - 'a'];
    if(ch == 0){
        ch = szof(trie);
        trie.pb(Node(L, trie[ptr].dep + 1));
        //cerr<<"new "<<ch<<" '"<<L<<"'"<<endl;
    }

    trie[ch].anc[0] = ptr;
    FOR(j, 1, 19, 1){
        trie[ch].anc[j] = trie[ trie[ch].anc[j-1] ].anc[j-1];
    }

    ptr = ch;
    pos.pb(ptr);
    //cerr<<"ptr = "<<ptr<<endl;
}

void UndoCommands(int U){
    int id = pos[szof(pos) - 1 - U];
    ptr = id;
    pos.pb(ptr);
    //cerr<<"ptr = "<<ptr<<endl;
}

char GetLetter(int P){
    int dis = trie[ptr].dep - P;
    int ret_node = ptr;
    FOR(j, 0, 19, 1){
        if(dis & (1<<j)) ret_node = trie[ret_node].anc[j];
    }
    char ret = trie[ret_node].val;
    return ret;
}

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