Submission #69809

#	Time	Username	Problem	Language	Result	Execution time	Memory
69809		Abelyan	Crayfish scrivener (IOI12_scrivener)	C++17	60 / 100	1050 ms	131940 KiB

scrivener

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

const int N=1000006,LG=20;
int parPow[N][LG],comNd[N],strSz[N];
char nd[N];
int cur=1,indCom;

void Init() {}

void TypeLetter(char L) {
    comNd[indCom+1]=cur;
    parPow[cur][0]=comNd[indCom];
    strSz[cur]=strSz[comNd[indCom]]+1;
    for (int i=1;i<LG;i++){
        parPow[cur][i]=parPow[parPow[cur][i-1]][i-1];
    }
    nd[cur]=L;
    cur++;
    indCom++;
    //cout<<indCom<<endl;
}

void UndoCommands(int u) {
    comNd[indCom+1]=comNd[indCom-u];
    indCom++;
}

char GetLetter(int p) {
    p=strSz[comNd[indCom]]-p-1;
    //cout<<p<<endl;
    int ans=comNd[indCom];
    for (int i=LG-1;i>=0;i--){
        if (p&(1<<i)){
            p-=(1<<i);
            ans=parPow[ans][i];
        }
    }
    //cout<<nd[ans]<<" ";
    return nd[ans];
}

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