Submission #559761

#	Time	Username	Problem	Language	Result	Execution time	Memory
559761		ngpin04	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	525 ms	137720 KiB

scrivener

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
const int N = 1e6 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

int ptr[N][26];
int anc[N][20];
int pos[N];
int d[N];
int cur,cnt,node;

char a[N];

//#include "grader.cpp"

void Init() {}

void TypeLetter(char L) {
    int v = L - 'a';
    if (!ptr[cur][v]) {
        ptr[cur][v] = ++node;
        a[node] = L;
        anc[node][0] = cur;
        for (int i = 1; i < 20; i++)
            anc[node][i] = anc[anc[node][i - 1]][i - 1];

        d[node] = d[cur] + 1;
    }

    cur = ptr[cur][v];
    pos[++cnt] = cur;
}

void UndoCommands(int U) {
    pos[cnt + 1] = pos[cnt - U];
    cnt++;
    cur = pos[cnt];
}

char GetLetter(int P) {
    int dis = d[cur] - (P + 1);
    int v = cur;
    for (int i = 0; i < 20; i++, dis >>= 1)
        if (dis & 1)
            v = anc[v][i]; 
    return a[v];
}

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