Submission #343921

#	Time	Username	Problem	Language	Result	Execution time	Memory
343921		bigDuck	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	569 ms	86764 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount




/*struct node{
    char c;
    int cnt;
    node *l, *r;

    node(node *l, node *r){
        this->l=l; this->r;
        this->cnt=l->cnt+r->cnt;
    }
    node(char c){
        this->c=c;
        this->cnt=1;
        this->l=NULL;
        this->r=NULL;
    }
} *ver[1000010];
*/


int tab[1000010][20];
int l[1000010];
char a[1000010];
int Tmp=1;



void add_char(char c){
    l[Tmp]=l[Tmp-1]+1;
    if(Tmp==1){
        a[Tmp]=c;
        Tmp++;
        return ;
    }

    a[Tmp]=c;
    tab[Tmp][0]=Tmp-1;
    for(int j=1; (j<=19) && (tab[Tmp][j-1]>0); j++){
        tab[Tmp][j]=tab[tab[Tmp][j-1] ][j-1];
    }
    Tmp++;
    return;
}






void Init() {

}




void TypeLetter(char L) {
    add_char(L);
}

void UndoCommands(int U){
    for(int j=0; j<=19; j++){tab[Tmp][j]=tab[Tmp-U-1][j];}
    l[Tmp]=l[Tmp-U-1];
    a[Tmp]=a[Tmp-U-1];
    Tmp++;
}

char GetLetter(int P) {

int p=l[Tmp-1]-(P+1)+1; p--;
int cr=Tmp-1;
//cout<<p<<"\n";
for(int j=19; (j>=0) && (p>0); j--){
    if( (p&(1ll<<j))>0 ){
        //cout<<cr<<"\n";
        cr=tab[cr][j]; p-=(1ll<<j);
    }
}
//cout<<cr<<" ";
//cout<<a[cr]<<"\n";
return a[cr];
}

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