Submission #589970

#	Time	Username	Problem	Language	Result	Execution time	Memory
589970		daria	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	467 ms	134216 KiB

scrivener

    #include "bits/stdc++.h"
    using namespace std;
    #define ll long long
    #define N (ll)1e6
     
    ll n = 0, t = 0;
    ll dpt[N], par[N][21], pos[N];
    char c[N];
   
    ll anc(ll a, ll p){
     for(ll i=0; i<21; ++i)
      if(p & (1 <<i))
       a = par[a][i];
     return a;
    }

    void Init(){
     
    }
     
    void TypeLetter(char L) {
     ll curr = pos[t];
     n++;
     t++;
     pos[t] = n;

     c[n] = L;
     dpt[n] = dpt[curr] + 1;
     
     par[n][0] = curr;
     for(ll i=1; i<21; ++i)
      par[n][i] = par[par[n][i-1]][i-1];    
    }
     
    void UndoCommands(int U) {
     t++;
     pos[t] = pos[t-U-1];

    }
     
    char GetLetter(int P){
     ll curr = pos[t];
     return c[anc(curr, dpt[curr]-P-1)];
    }

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