Submission #1216338

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216338		moondarkside	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	581 ms	83820 KiB

scrivener

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

struct character{
    int depht;
    char letter;
    vector<int> Pointers;
};

std::vector<int> Top;
vector<struct character> Tree;


void Init(){
    return;
}

int getPointerAtDepht(int start,int depht){
    if(Tree[start].depht==depht){
        return start;
    }
    int fix=Tree[start].depht-depht;
    int i=-1;
    for(;fix>0;i++){
        fix/=2;
    }
    return getPointerAtDepht(Tree[start].Pointers[i],depht);
    
}

void TypeLetter(char L){
    if(Top.size()==0 || Top[Top.size()-1]==-1){
        Tree.push_back({0,L,vector<int>()});
    }
    else{
        
        int prevP=Top[Top.size()-1];
        int depht=Tree[prevP].depht+1;
        vector<int> Np;
        
        int pos=0;
        Np.push_back(prevP);
        while(Tree[prevP].Pointers.size()>pos){
            prevP=Tree[prevP].Pointers[pos];
            Np.push_back(prevP);
            pos+=1;
        }
        Tree.push_back({depht,L,Np});
        
        
    }
    Top.push_back(Tree.size()-1);
}


void UndoCommands(int U){
    if(U==Top.size()){
        Top.push_back(-1);
    }
    else{
        Top.push_back(Top[Top.size()-1-U]);
    }
}

char GetLetter(int P){
    int pt=getPointerAtDepht(Top[Top.size()-1],P);
    char tmp=Tree[pt].letter;
    return Tree[pt].letter;
}

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