Submission #609228

#	Time	Username	Problem	Language	Result	Execution time	Memory
609228		neki	Crayfish scrivener (IOI12_scrivener)	C++14	0 / 100	1 ms	852 KiB

scrivener

#include <bits/stdc++.h>
#define vc vector

using namespace std;

const int lg=20;

struct node{
    char c;
    node* anc[lg];
    int hei;
    node(char c_, node* par, int hei_){
        c=c_;hei=hei_;
        if(par==NULL) anc[0]=this;
        else anc[0]=par;
        for(int i=1;i<lg;++i) anc[i] = (anc[i-1]->anc)[i-1];
    }
    char getkth(int ind){
        node* ret =this;
        ind=hei-1 -ind;
        for(int i=lg-1;i>=0;--i) if(ind&(1<<i)) ret=ret->anc[i]; 
        return ret->c;
    }
};
vc<node> tr;

vc<node*> tpoi;
node* cur;

void Init(){
    tr.push_back(node('.', NULL, 0)); 
    cur=(&tr[tr.size()-1]);
    //cout << cur->c << endl;
}
void TypeLetter(char L){
    tr.push_back(node(L, cur, cur->hei +1));
    cur=(&tr[tr.size()-1]);
    tpoi.push_back(cur);
}
void UndoCommands(int U){ 
    tpoi.push_back(tpoi[tpoi.size()-1 - U]);
    cur=tpoi.back();
}
char GetLetter(int P){
    return cur->getkth(P);
}

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