Submission #43802

#	Time	Username	Problem	Language	Result	Execution time	Memory
43802		PowerOfNinjaGo	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	652 ms	150388 KiB

scrivener

//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
    #include "grader.cpp"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii;
#define X first
#define Y second
#define vi vector<int>
#define vii vector< ii >
#define pb push_back
const int maxn = 1e6+5;
int dp[25][maxn];
char txt[maxn];
int sz[maxn];
int ver[maxn];
int rounds = 1;
int n = 1;
void Init()
{
    return;
}

int kth(int u, int k)
{
    for(int i = 22; i>= 0; i--)
    {
        if((1<<i)<= k)
        {
            u = dp[i][u];
            k -= 1<<i;
        }
    }
    return u;
}
void TypeLetter(char L)
{
    int lver = ver[rounds-1];
    dp[0][n] = lver;
    for(int i = 1; i<= 22; i++) dp[i][n] = dp[i-1][dp[i-1][n]];
    sz[n] = 1+sz[lver];
    //printf("sz[%d] = %d\n", n, sz[n]);
    //printf("ver[%d] = %d\n", rounds, n);
    txt[n] = L;
    ver[rounds] = n;
    rounds++; n++;
}

void UndoCommands(int U)
{
    int want = ver[rounds-U-1];
    ver[rounds] = want;
    rounds++;
}

char GetLetter(int P)
{
    P = sz[ver[rounds-1]]-P-1;
    //printf("P is %d\n", P);
    int tmp = kth(ver[rounds-1], P);
    return txt[tmp];
}

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