Submission #250331

#	Time	Username	Problem	Language	Result	Execution time	Memory
250331		eohomegrownapps	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	412 ms	71168 KiB

scrivener

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

vector<char> ind2letter; //0th char -- nothing
int curind = 0;
vector<int> depth; //depth of node, length of string
vector<int> seq;
int kthparent[21][1000000];

void Init() {
    depth.push_back(0);
    ind2letter.push_back('.');
    seq.push_back(curind);
    for (int i = 0; i<21; i++){
        kthparent[i][curind]=-1;
    }
    curind++;
}

void TypeLetter(char L) {
    seq.push_back(curind);
    ind2letter.push_back(L);
    kthparent[0][curind]=seq[seq.size()-2];
    for (int i = 1; i<21; i++){
        if (kthparent[i-1][curind]==-1){
            kthparent[i][curind]=-1;
        } else {
            kthparent[i][curind]=kthparent[i-1][kthparent[i-1][curind]];
        }
    }
    depth.push_back(depth[kthparent[0][curind]]+1);
    curind++;
}

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

int getkthparent(int node, int k){
    for (int i = 0; i<21; i++){
        if ((1<<i)&k){
            node=kthparent[i][node];
        }
        if (node==-1){
            return -1;
        }
    }
    return node;
}

char GetLetter(int P) {
    int start = seq[seq.size()-1];
    int node = getkthparent(start, depth[start]-P-1);
    return ind2letter[node];
}

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