Submission #1309369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309369		shirokito	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	380 ms	73936 KiB

scrivener

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

#define all(a) (a).begin(), (a).end()

using ll = long long;

const int N = 1e6 + 24, LG = 24;

int n, par[N][LG], h[N], cur;
char value[N];
vector<int> history;

void Init() {
    n = 0;
    history.push_back(0);
    h[0] = 0;
    cur = 0;
}

void TypeLetter(char L) {
    int v = ++n;

    value[v] = L;
    h[v] = h[cur] + 1;

    par[v][0] = cur;
    for (int j = 1; j < LG; j++) {
        par[v][j] = par[par[v][j - 1]][j - 1];
    }

    history.push_back(v);

    cur = v;
}

void UndoCommands(int U) {
    int sz = (int)history.size();
    cur = history[sz - U - 1];
    history.push_back(cur);
}

char GetLetter(int P) {
    int k = h[cur] - P - 1;
    int u = cur;

    for (int j = 0; j < LG; j++) {
        if ((k >> j) & 1) {
            u = par[u][j];
        }
    }

    return value[u];
}

#ifdef LOCAL

void solve() {
    int q; cin >> q;

    Init();

    while (q--) {
        char t; cin >> t;

        if (t == 'T') {
            char c; cin >> c;
            TypeLetter(c);
        }
        else if (t == 'U') {
            int k; cin >> k;
            UndoCommands(k);
        }
        else {
            int p; cin >> p;
            cout << GetLetter(p) << endl;
        }
    }
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 1; // cin >> T;
    while (T--) {
        solve();
    }
}

#endif

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