Submission #574105

#	Time	Username	Problem	Language	Result	Execution time	Memory
574105		ogibogi2004	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	484 ms	90672 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+6;
struct trie
{
    char what[MAXN];
    int sz[MAXN];
    int nxt[MAXN];
    int cur;
    int par[MAXN][20];
    void add_letter(char c)
    {
        nxt[cur]=cur+1;
        par[cur+1][0]=cur;
        sz[cur+1]=sz[cur]+1;
        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];
        sz[cur+1]=sz[cur-u];
        cur++;

    }
    char GetLetter(int p)
    {
        int d=sz[cur]-p,c1=cur;
        for(int i=0;i<20;i++)
        {
            if(d&(1<<i))c1=par[c1][i];
        }
        //cout<<sz[cur]<<" "<<p<<" "<<d<<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: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40