Submission #520342

#	Time	Username	Problem	Language	Result	Execution time	Memory
520342		krit3379	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	431 ms	89540 KiB

scrivener

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

struct A{
    char c;
    int len,p[20];
}s[N];

int sz;

void Init(){}

void TypeLetter(char c){
    s[sz+1]={c,s[sz].len+1,sz};
  	sz++;
    for(int i=1;i<20;i++)
        s[sz].p[i]=s[s[sz].p[i-1]].p[i-1];
}

void UndoCommands(int u){
    s[sz+1]=s[sz-u];
    sz++;
}

char GetLetter(int p){
    int now=sz;
    p=s[now].len-p-1;
    for(int i=0;i<20;i++)
        if(p&(1<<i))
        now=s[now].p[i];
    return s[now].c;
}

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