Submission #553357

#	Time	Username	Problem	Language	Result	Execution time	Memory
553357		pokmui9909	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	564 ms	139856 KiB

scrivener

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

ll Q;
ll P[1000005][22];
char C[1000005];
ll D[1000005];
ll n = 0, m = 0;
vector<ll> V;
void Init(){}
void TypeLetter(char c){
  	m++;
    C[m] = c;
    V.push_back(m);
    D[m] = D[n] + 1;
    P[m][0] = n;
    for(ll j = 1; j < 22; j++){
        P[m][j] = P[P[m][j - 1]][j - 1];
    }
    n = m;
}
void UndoCommands(int k){
    n = V[V.size() - 1 - k];
    V.push_back(n);
}
char GetLetter(int k){
    k = D[n] - k - 1;
    ll u = n;
    for(ll j = 0; j < 22; j++){
        if(k & (1 << j)){
            u = P[u][j];
        }
    }
    return C[u];
}

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