Submission #62912

#	Time	Username	Problem	Language	Result	Execution time	Memory
62912		theknife2001	Crayfish scrivener (IOI12_scrivener)	C++17	0 / 100	1065 ms	263168 KiB

scrivener

//#include <bits/stdc++.h>
//
//using namespace std;
//const int N=1e6+5;
//int a[N];
//char b[N];
//int c[N];
//char s[N];
//int cnt;
//int k=0;
//
//
//void Init() {}
//
//void TypeLetter(char L) {
//    a[k]=1;
//    b[k]=L;
//    k++;
//}
//
//void UndoCommands(int U) {
//    a[k]=2;
//    c[k]=U;
//    k++;
//}
//
//char GetLetter(int P) {
//    if(cnt==0)
//    {
//        int j=0;
//        k--;
//        while(k>=0)
//        {
//            if(a[k]==1)
//            {
//                s[j]=b[k];
//                j++;
//            }
//            else if(a[k]==2)
//            {
//                k=k-c[k];
//            }
//            else
//            {
//                cout<<k<<endl;
//                assert(0);
//            }
//            k--;
//        }
//        reverse(s,s+j);
//    }
//    cnt=1;
//    return s[P];
//}
#include <bits/stdc++.h>


using namespace std;
const int N=1e6+55;
int trie[N*4][26];
char letter[N];
int p[N][22];
int a[N];
int l[N];
int node;
int cnt=1;
int k;

void Init()
{
    node=cnt++;
    memset(trie,-1,sizeof trie);
}


void TypeLetter(char L)
{
    int c=L-'a';
    int temp=node;
    if(trie[node][c]==-1)
        trie[node][c]=cnt++;
    letter[node]=c;
    node=trie[node][c];
    a[k]=node;
    l[k]=l[k-1]+1;
    p[node][0]=temp;
    for(int i=1;i<=21;i++)
        p[node][i]=p[p[node][i-1]][i-1];
    k++;
}

void UndoCommands(int U)
{
    node=a[k-U];
    l[k]=l[k-U];
    a[k]=node;
    k++;
}
char GetLetter(int P)
{
    P=l[k-1]-P;
    for(int i=21;i>=0;i--)
    {
        if(P&(1<<i))
            P=p[node][i];
    }
    return letter[P];
}

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