Submission #1220574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220574		Rafael_Augusto	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	543 ms	94448 KiB

scrivener

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

//#define int long long
#define pb push_back
#define f first
#define s second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define fall(i, s, n) for(int i=s; i<n; i++)
#define rfall(i, s, n) for(int i=s; i>=n; i--)

typedef pair<int, int> pii;
typedef tuple<int, int, int> trio;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e6 + 7;
const int MAXL = 23;

int sz[MAXN];
char last[MAXN];
int sparse[MAXN][MAXL], t=1;

void build(){
    fall(i, 1, MAXL) sparse[t][i] = sparse[sparse[t][i-1]][i-1];
}

void Init() {}

void TypeLetter(char L) {
    last[t] = L, sz[t] = sz[t-1]+1, sparse[t][0]=t-1;
    build(), t++;
}

void UndoCommands(int U) {
    last[t] = last[t-U-1], sz[t]=sz[t-U-1], sparse[t][0]=t-U-1;
    build(), t++;
}

char GetLetter(int P) {
    int x=t-1, s=sz[t-1];

    rfall(i, MAXL-1, 0)
        if(sparse[x][i] && sz[sparse[x][i]] >= P+1) s = sz[sparse[x][i]], x = sparse[x][i];
    
    return last[x];
}

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