Submission #1255646

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255646		Art	Crayfish scrivener (IOI12_scrivener)	C++17	60 / 100	1095 ms	82620 KiB

scrivener

//      - Art -
#include <bits/stdc++.h>

#define el              cout << '\n'

#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c)       for (int i = 0, _c = (c); i < _c; ++i)

const int N = 1e6 + 7;

using namespace std;

char ans[N];
int sz, depth[N], par[N][20];

void Init() {
    par[0][0] = 0;
}

void TypeLetter(char L) {
    ans[++sz] = L;
    par[sz][0] = sz - 1;
    depth[sz] = depth[sz - 1] + 1;
//    FOR (j, 1, 19) {
    for (int j = 1; j <= 19; ++j) {
        par[sz][j] = par[par[sz][j - 1]][j - 1];
    }
}

void UndoCommands(int U) {
    ans[++sz] = 'X';
    par[sz][0] = sz - U - 1;
    depth[sz] = depth[sz - U - 1];
//    FOR (j, 1, 19) {
    for (int j = 1; j <= 19; ++j) {
        par[sz][j] = par[par[sz][j - 1]][j - 1];
    }
}

int lift(int u, int k) {
//    REV (i, 19, 0) {
    for (int i = 19; i >= 0; --i) {
        if (depth[par[u][i]] >= k) {
            u = par[u][i];
        }
    }
    return u;
}

char GetLetter(int P) {
    ++P; // 1-based idx
    return ans[lift(sz, P)];
}

// int main() {

//     #define name "scrivener"
//     if (fopen(name".inp", "r")) {
//         freopen(name".inp", "r", stdin);
//         freopen(name".out", "w", stdout);
//     }

//     ios_base::sync_with_stdio(false);
//     cin.tie(0); cout.tie(0);

//     int subtask;
//     cin >> subtask;
//     int q;
//     cin >> q;
//     while (q--) {
//         char tp;
//         cin >> tp;
//         if (tp == 'T') {
//             char c;
//             cin >> c;
//             TypeLetter(c);
//         }
//         else if (tp == 'U') {
//             int k;
//             cin >> k;
//             UndoCommands(k);
//         }
//         else {
//             int i;
//             cin >> i;
//             cout << GetLetter(i);
//         }
//     }

//     return 0;
// }

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