Submission #317794

#	Time	Username	Problem	Language	Result	Execution time	Memory
317794		mohamedsobhi777	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1061 ms	73824 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 7;
char last;
void Init() {}

int cnt, cur = 0;
int trie[N][27];
vector<int> hist = {0};
int prv[N];
int chs[N];
int val[N];

void TypeLetter(char L)
{
        L -= 'a';
        trie[cur][L] = ++cnt;
        hist.push_back(cnt);
        prv[cnt] = cur;
        val[cnt] = val[cur] + 1;
        chs[cnt] = L;
        cur = cnt;
}

void UndoCommands(int U)
{
        cur = hist[hist.size() - U - 1];
        hist.push_back(cur);
}

char GetLetter(int P)
{
        P++;
        int now = cur;
        while (val[now] > P)
                now = prv[now];
        return char(chs[now] + 'a');
}

Compilation message (stderr)

scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:19:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   19 |         trie[cur][L] = ++cnt;
      |                   ^

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