Submission #574101

#	Time	Username	Problem	Language	Result	Execution time	Memory
574101		ogibogi2004	Crayfish scrivener (IOI12_scrivener)	C++14	5 / 100	1088 ms	59656 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+6;
struct trie
{
    char what[MAXN];
    int nxt[MAXN];
    int cur;
    int par[MAXN][20];
    void add_letter(char c)
    {
        nxt[cur]=cur+1;
        par[cur+1][0]=cur;
        cur++;
        what[cur]=c;
        for(int step=1;step<20;step++)
        {
            par[cur][step]=par[par[cur][step-1]][step-1];
        }
    }
    void undoOperations(int u)
    {
        nxt[cur+1]=nxt[cur-u];
        par[nxt[cur+1]][0]=cur+1;
        for(int j=0;j<20;j++)par[cur+1][j]=par[cur-u][j];
        //nxt[par[cur+1][0]]=cur+1;
        what[cur+1]=what[cur-u];
        cur++;

    }
    char GetLetter(int p)
    {
        int c1=0;
        for(int j=0;j<p;j++)
        {
            c1=nxt[c1];
            //cout<<" - "<<c1<<endl;
        }
        return what[c1];
    }
    void print()
    {
        cout<<cur<<" "<<what[cur]<<endl;
    }
}t;

char last;

void Init() {
t.cur=0;
}

void TypeLetter(char L) {
   t.add_letter(L);
}

void UndoCommands(int U) {
    t.undoOperations(U);
}

char GetLetter(int P) {
    return t.GetLetter(P+1);
}
/*
14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2
*/

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