Submission #1097366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097366		MtSaka	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	507 ms	180052 KiB

scrivener

#include"bits/stdc++.h"
//#include"scrivener.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
struct Node{
    int val;
    int sz;
    int table[20]={};
    Node(){
        sz=0,val=-1;
        rep(i,20)table[i]=0;
    }
};
Node nodes[2000000];
int idx;
void Init() {
    idx=1;
    nodes[0]=Node();
}

void TypeLetter(char L) {
    nodes[idx]=Node();
    nodes[idx].val=L-'a';
    nodes[idx].sz=nodes[idx-1].sz+1;
    nodes[idx].table[0]=idx-1;
    rep(i,1,20)nodes[idx].table[i]=nodes[nodes[idx].table[i-1]].table[i-1];
    idx++;
}

void UndoCommands(int U) {
    //cerr<<"Undo Commands "<<U<<endl;
    nodes[idx]=nodes[idx-1-U];
    idx++;
    //cerr<<sz<<endl;
}


char GetLetter(int P) {
    //cerr<<"Get Letter "<<P<<endl;
    int now=idx-1;
    rrep(i,20){
        if(nodes[nodes[now].table[i]].sz>=P+1){
            now=nodes[now].table[i];
        }
    }
    return nodes[now].val+'a';
}

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