Submission #235610

#	Time	Username	Problem	Language	Result	Execution time	Memory
235610		Dremix10	Crayfish scrivener (IOI12_scrivener)	C++17	5 / 100	494 ms	119420 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];
    }
    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;
}

Compilation message (stderr)

scrivener.cpp: In function 'void UndoCommands(int)':
scrivener.cpp:47:9: warning: unused variable 'i' [-Wunused-variable]
     int i;
         ^

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