Submission #897887

#	Time	Username	Problem	Language	Result	Execution time	Memory
897887		aykhn	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	339 ms	166848 KiB

scrivener

#include <bits/stdc++.h>
 
// author: aykhn
 
using namespace std;
 
#define mpr make_pair
#define pb push_back
#define fi first
#define se second
 
const int MXN = 1e6 + 5;
const int LOG = 21;
 
int n;
int adj[MXN][26];
int p[LOG][MXN];
char val[MXN];
int dep[MXN];
vector<int> s;
 
void Init() 
{
    s.clear();
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j < LOG; j++) p[j][i] = 0;
        for (int j = 0; j < 26; j++) adj[i][j] = 0;
        val[i] = '$';
    }
    s.pb(0);
    n = 0;
}
 
void TypeLetter(char L) 
{
    int cur = s.back();
    if (adj[cur][L - 'a']) s.pb(adj[cur][L - 'a']);
    else 
    {
        adj[cur][L - 'a'] = ++n;
        p[0][n] = cur;
        for (int i = 1; i < LOG; i++) p[i][n] = p[i - 1][p[i - 1][n]];
        dep[n] = dep[cur] + 1;
        val[n] = L;
        s.pb(n);
    }
}
 
void UndoCommands(int U) 
{
    s.pb(s[(int)s.size() - U - 1]);
}
 
char GetLetter(int P) 
{   
    int cur = s.back();
    int d = dep[cur] - P - 1;
    for (int i = LOG - 1; i >= 0; i--)
    {
        if (d >> i & 1) cur = p[i][cur];
    }
    return val[cur];
}

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