Submission #550650

#	Time	Username	Problem	Language	Result	Execution time	Memory
550650		David_M	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	436 ms	86724 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

int curr, last=-1, h[1000006], pa[20][1000006];
char C[1000006];

void add(int x, char c){

    last++;
    pa[0][last]=curr;
    h[last]=h[curr]+1;
    curr=last;
    C[curr]=c;
    for (int i=1; i<20; i++){
        pa[i][curr]=pa[i-1][pa[i-1][curr]];
    }

}

void roll_back(int t){
    curr=++last;
    h[curr]=h[t];
    C[curr]=C[t];
    for (int i=0; i<20; i++){
        pa[i][curr]=pa[i][t];
    }
}

int Kth_parent(int k){
    int Pa=curr;
    for (int i=19; i>=0; i--){
        if(k&(1<<i))Pa=pa[i][Pa];
    }
    return C[Pa];
}

void Init() { h[0]=-1; }

string s;

void TypeLetter(char L) { add(curr, L); }
void UndoCommands(int U) { roll_back(last-U); }
char GetLetter(int P) { return Kth_parent(h[curr]-P); }

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