Submission #311088

#	Time	Username	Problem	Language	Result	Execution time	Memory
311088		talant117408	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	978 ms	66856 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef pair <ll, ll> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (int)(v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int N = 1e7+7;
int up[N][20], loc[N], depth[N], timer, letnum, curloc;
char node[N];

void Init(){
    
}

void TypeLetter(char L) {
    node[++letnum] = L;
    up[letnum][0] = curloc;
    loc[++timer] = letnum;
    depth[letnum] = depth[curloc]+1;
    for(int i = 1; i < 20; i++){
        up[letnum][i] = up[up[letnum][i-1]][i-1];
    }
    curloc = letnum;
}

void UndoCommands(int U) {
    curloc = loc[timer-U];
    loc[++timer] = curloc;
}

char GetLetter(int P){
    P++;
    int to = curloc;
    for(int i = 19; i >= 0; i--){
        if(depth[up[to][i]] >= P){
            to = up[to][i];
        }
    }
    return node[to];
}

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