Submission #578339

#	Time	Username	Problem	Language	Result	Execution time	Memory
578339		Half	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	749 ms	224704 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"WAFFLES "<<i<<"<\n"
#define INF 1000000000000000000LL
#define EPS (0.00000000001L)
#define pi (3.141592653589793L)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;

template<class A=pair<int, int> >
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i].ff << "," << a[i].ss <<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}

vector<vector<ll> > anc;
vector<ll> dpth;
vector<pair<ll, char> > trie;
vector<ll> hist;
ll curr = -1;

ll addNode(ll pr, char c){
  trie.pb({pr, c});
  anc.pb({});
  if(pr == -1){
    dpth.pb(1);
    return trie.size()-1;
  }else{
    dpth.pb(dpth[pr]+1);
  }
  anc.back().pb(pr);
  ll mvup = pr;
  ll n = 1;
  while(1<<n < dpth.back()){
    mvup = anc[mvup][n-1];
    anc.back().pb(mvup);
    n++;
  }
  return trie.size()-1;
}

ll upLift(ll cr, ll n){
  ll bt = 0;
  while(n > 0){
    if(n & (1<<bt)){
      cr = anc[cr][bt];
      n -= (1<<bt);
    }
    bt++;
  }
  return cr;
}

void Init() {
  
}

void TypeLetter(char L) {
  curr = addNode(curr, L);
  hist.pb(curr);
}

void UndoCommands(int U) {
  curr = hist[hist.size()-U-1];
  hist.pb(curr);
}

char GetLetter(int P) {
  return trie[upLift(curr,dpth[curr]-P-1)].ss;
}

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