Submission #609366

#	Time	Username	Problem	Language	Result	Execution time	Memory
609366		neki	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	534 ms	144528 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-ind;
        for(int i=0;i<lg;++i){ if(ind&(1<<i)) ret=(ret->anc[i]); assert(ret!=NULL);}
        return ret->c;
    }
};

vc<node*> tpoi;
node* cur;

void Init(){
    cur = new node('.', NULL, 0);
    tpoi.push_back(cur);
}
void TypeLetter(char L){
    cur = new node(L, cur, (cur->hei) +1);
    tpoi.push_back(cur);
}
void UndoCommands(int U){
    cur = tpoi[tpoi.size()-1 - U];
    tpoi.push_back(cur);
}
char GetLetter(int P){
    return cur->getkth(P+1);
}

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