Submission #967350

#	Time	Username	Problem	Language	Result	Execution time	Memory
967350		irmuun	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	303 ms	71868 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

const int N=1e6+5,lg=21;
int par[N][lg],d[N],pos[N];
char ch[N];

int cur=0,dep=0,now=0,com=0;
void Init(){
    return;
}
void TypeLetter(char L){
    cur++;
    com++;
    pos[com]=cur;
    ch[cur]=L;
    par[cur][0]=now;
    now=cur;
    dep++;
    d[now]=dep;
    int k=2,l=1;
    while(k<=dep){
        par[cur][l]=par[par[cur][l-1]][l-1];
        l++;
        k*=2;
    }
    return;
}
void UndoCommands(int U){
    U=pos[com-U];
    com++;
    pos[com]=U;
    now=U;
    dep=d[U];
    return;
}
char GetLetter(int P){
    int up=d[now]-P-1;
    int r=now;
    for(int i=20;i>=0;i--){
        if(up&(1<<i)){
            r=par[r][i];
        }
    }
    return ch[r];
}

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