Submission #1097353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097353		MtSaka	Crayfish scrivener (IOI12_scrivener)	C++17	0 / 100	375 ms	261792 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 ch[2]={};
    Node():val(-1){
        ch[0]=ch[1]=-1;
    }
};
Node nodes[10000000];
int sz;
void destructive_set(Node&nd,int idx,int val){
    if(idx==0)nd.val=val;
    if(nd.ch[idx&1]==-1)nd.ch[idx&1]=sz,nodes[sz++]=Node();
    else destructive_set(nodes[nd.ch[idx&1]],idx>>1,val);
}
void build(const vector<int>&a){
    for(int i=0;i<(int)a.size();++i){
        destructive_set(nodes[0],i,a[i]);
    }
}
int change(const Node&nd,int idx,int val){
    int res=sz;
    Node&ret=nodes[sz++];
    ret.ch[0]=nd.ch[0],ret.ch[1]=nd.ch[1];
    if(idx==0){
        ret.val=val;
    }
    else{
        if(ret.ch[idx&1]==-1){
            ret.ch[idx&1]=sz;
            nodes[sz++]=Node();
        }
        ret.ch[idx&1]=change(nodes[ret.ch[idx&1]],idx>>1,val);
    }
    return res;
}
int get(const Node&nd,int idx){
    if(idx==0)return nd.val;
    if(nd.ch[idx&1]==-1)return -1;
    return get(nodes[nd.ch[idx&1]],idx>>1);
}

vector<pair<int,Node>>st;
void Init() {
    st.clear();
    sz=1;
    nodes[0]=Node();
    st.eb(0,nodes[0]);
}

void TypeLetter(char L) {
    //cerr<<"Type Letter "<<L<<endl;
    int len=st.back().first;
    Node&nd=st.back().second;
    st.emplace_back(len+1,nodes[change(nd,len,L-'a')]);
    //cerr<<sz<<endl;
}

void UndoCommands(int U) {
    //cerr<<"Undo Commands "<<U<<endl;
    assert(st.size()>=U);
    st.emplace_back(st[st.size()-1-U]);
    //cerr<<sz<<endl;
}


char GetLetter(int P) {
    //cerr<<"Get Letter "<<P<<endl;
    return 'a'+get(st.back().second,P);
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from scrivener.cpp:1:
scrivener.cpp: In function 'void UndoCommands(int)':
scrivener.cpp:83:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, Node> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |     assert(st.size()>=U);
      |            ~~~~~~~~~^~~

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