Submission #917649

#	Time	Username	Problem	Language	Result	Execution time	Memory
917649		anton	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	865 ms	135576 KiB

scrivener

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

#define ll long long
char last;

struct CMD{
    vector<int> prev;
    int depth;
    char added;
    int rep;
    CMD(){
        prev.resize(20, 0);
        added = ' ';
        depth = 0;
        rep = 0;
    }
};

vector<CMD> tree;

void add_to_tree(int _prev, char _added){
    CMD r;
    r.prev[0] = _prev;
    r.added = _added;
    r.depth = tree[_prev].depth +1;
    r.rep = tree.size();
    for(int i = 1; i<20; i++){
        r.prev[i] = tree[r.prev[i-1]].prev[i-1];
    }
    tree.push_back(r);
}
string s;

void Init() {
    tree.push_back(CMD());
}

void TypeLetter(char L) {
  last = L;
  add_to_tree(tree.back().rep, last);

}

void UndoCommands(int U) {
  tree.push_back(CMD());
  tree.back().rep = tree[tree.size()-2-U].rep;
}

char get_anc(int id, int dist){
    int cur = id;
    for(int i = 19; i>=0; i--){
        if((dist & (1<<i))!=0){
            cur = tree[cur].prev[i];
        }
    }
    return tree[cur].added;
}

char GetLetter(int P) {
    return get_anc(tree.back().rep, tree[tree.back().rep].depth-P-1);
}

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