Submission #747862

#	Time	Username	Problem	Language	Result	Execution time	Memory
747862		Hacv16	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	948 ms	87108 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

const int MAX = 1e6 + 15;
const int LOG = 21;

int dp[MAX][LOG], tam[MAX], cnt;
char letter[MAX];

void Init(){ }

void calcLift(int curNode){
    for(int j = 1; j < LOG; j++)
        dp[curNode][j] = dp[ dp[curNode][j - 1] ][j - 1];
}

void TypeLetter(char L){
    int curNode = ++cnt;
    letter[curNode] = L;

    dp[curNode][0] = cnt - 1;
    tam[curNode] = tam[cnt - 1] + 1;

    calcLift(curNode);
}

void UndoCommands(int U){
    int curNode = ++cnt;

    dp[curNode][0] = cnt - 1 - U;
    tam[curNode] = tam[dp[curNode][0]];

    calcLift(curNode);
}

char GetLetter(int P){
    int curNode = cnt; P++;

    for(int j = LOG - 1; j >= 0; j--)
        if(tam[ dp[curNode][j] ] >= P && dp[curNode][j] > 0)
            curNode = dp[curNode][j];

    return letter[curNode];
}

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