Submission #422029

#	Time	Username	Problem	Language	Result	Execution time	Memory
422029		Lobo	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	570 ms	78300 KiB

scrivener

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

const long long INFll = 1e18+10;
const int INFii = 1e9+10;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back

#define maxn 1000100
#define log 22
//LEMBRAR DE MUDAR

ii n, tmp, p[maxn][log+2], t[maxn], h[maxn];
char c[maxn];

void TypeLetter(char L) {
    n++;
    tmp++;
    t[tmp] = n;
    c[n] = L;

    p[n][0] = t[tmp-1];
    h[n] = h[t[tmp-1]] + 1;

    for(ii i = 1; i <= log; i++) {
        p[n][i] = p[p[n][i-1]][i-1];
    }

    //cout << L << " " << n << " " << tmp << " -> " << h[n] << endl;
}

void UndoCommands(int U) {
    tmp++;
    t[tmp] = t[tmp-U-1];
}

char GetLetter(int P) {
    ii u = t[tmp];
    P = h[t[tmp]]-P-1;

    for(ii i = log; i >= 0; i--) {
        if(P-(1<<i) >= 0) {
            P-= (1<<i);
            u = p[u][i];
        }
    }

    return c[u];
}

void Init() {

}

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