Submission #71759

#	Time	Username	Problem	Language	Result	Execution time	Memory
71759		RezwanArefin01	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1052 ms	180196 KiB

scrivener

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

const int N = 1e6 + 10; 

int t[N][26], p[N][21], idx, d[N];
int tym, node[N];  
char c[N]; 

void Init() {}

void TypeLetter(char L) {
    int u = node[tym]; 
    int &v = t[u][L - 'a'];
    if(!v) {
        v = ++idx;
        p[v][0] = u; 
        for(int i = 1; i <= 20; i++) 
            p[v][i] = p[p[v][i - 1]][i - 1]; 
    } c[v] = L; 
    node[++tym] = v; 
    d[v] = d[u] + 1; 
}

void UndoCommands(int U) {
    int u = node[tym - U]; 
    node[++tym] = u;
}

char GetLetter(int P) {
    int u = node[tym]; 
    int k = d[u] - P - 1;
    for(int i = 20; i >= 0; i--) 
        if(k >> i & 1) u = p[u][i]; 
    return c[u]; 
}

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