Submission #1207487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207487		boss_zz	Crayfish scrivener (IOI12_scrivener)	C++20	100 / 100	362 ms	205012 KiB

scrivener

#include<bits/stdc++.h>
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define ll int
#define ff first 
#define ss second 
#define mp make_pair 
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll N=1e6+5,inf=1e9;
ll nxt[N][26],timer,ver[N],J[N][25],root,cnt,cur;
char ch[N];
ll cal(){
    ll res=1,v=cur;
    for(ll i=20;i>=0;--i){
        if(J[v][i]){
            v=J[v][i];
            res+=1LL<<i;
        }
    }
    return res;
}
void Init(){
    ver[0]=0;
    root=0;
    cur=0;
    cnt=0;
    timer=0;
    rep(i,0,N-1) rep(j,0,24) J[i][j]=0;
    rep(i,0,N-1) rep(j,0,25) nxt[i][j]=0;
    rep(i,0,N-1) ver[i]=0;
}
void TypeLetter(char x){
    cnt++;
    ll c=x-'a';
    if(!nxt[ver[cnt-1]][c]) nxt[ver[cnt-1]][c]=++timer;
    cur=ver[cnt]=nxt[ver[cnt-1]][c];
    ch[ver[cnt]]=x;
    J[ver[cnt]][0]=ver[cnt-1];
    rep(j,1,20) J[ver[cnt]][j]=J[J[ver[cnt]][j-1]][j-1];
}
void UndoCommands(int x){
    cnt++;
    cur=ver[cnt]=ver[cnt-1-x];
}
char GetLetter(int x){
    ll n=cal();
    ll step=n-x-1,v=cur;
    rep(i,0,20) if(step&(1LL<<i)) v=J[v][i];
    return ch[v];
}

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