Submission #235612

#	Time	Username	Problem	Language	Result	Execution time	Memory
235612		Dremix10	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	629 ms	145632 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
#define N (int)1e6+1
#define maxp 22

struct ano{

char c;
int sons[26];

};

ano trie[N+1];
int curr=0;
int t=1;
int lift[N+1][maxp];
int googleChrome[N+1];
int d[N+1];
int cnt=1;

void Init() {

}

void TypeLetter(char c) {
    int next=trie[curr].sons[c-'a'];
    if(next==0){
        trie[curr].sons[c-'a']=cnt;
        d[cnt]=d[curr]+1;

        trie[cnt].c=c;
        lift[cnt][0]=curr;
        curr=cnt;
        int i;
        for(i=1;i<maxp;i++)
            lift[curr][i]=lift[lift[curr][i-1]][i-1];
        cnt++;
    }
    else
        curr=next;

    googleChrome[t++]=curr;
   // cout<<t<<" "<<curr<<" "<<trie[curr].c<<endl;
}

void UndoCommands(int n) {
    curr=googleChrome[t-n-1];
   // int i;
  //  for(i=1;i<t;i++)
  //      cout<<googleChrome[i]<<" ";
  //  cout<<endl;
    googleChrome[t++]=curr;
    //cout<<t<<" "<<curr<<" "<<trie[curr].c<<endl;
}

char GetLetter(int x) {
    //cout<<d[curr]<<" "<<curr<<endl;
    int k=d[curr]-x-1;
    int i;
    int ans=curr;
    for(i=maxp-1;i>=0;i--)
    if(k>=(1<<i)){
        k-=(1<<i);
        ans=lift[ans][i];
    }
  //  cout<<ans<<endl;
    return trie[ans].c;
}

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