Submission #574094

#	Time	Username	Problem	Language	Result	Execution time	Memory
574094		ogibogi2004	Crayfish scrivener (IOI12_scrivener)	C++14	12 / 100	1086 ms	62864 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 d=cur-p,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);
   //t.print();
   //cout<<t.par[t.cur][0]<<" "<<t.nxt[t.par[t.cur][0]]<<endl;
}

void UndoCommands(int U) {
    t.undoOperations(U);
    //t.print();
    //cout<<t.par[t.cur][0]<<" "<<t.nxt[t.par[t.cur][0]]<<endl;
}

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
*/

Compilation message (stderr)

scrivener.cpp: In member function 'char trie::GetLetter(int)':
scrivener.cpp:34:13: warning: unused variable 'd' [-Wunused-variable]
   34 |         int d=cur-p,c1=0;
      |             ^

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