Submission #261003

#	Time	Username	Problem	Language	Result	Execution time	Memory
261003		georgerapeanu	Crayfish scrivener (IOI12_scrivener)	C++11	100 / 100	824 ms	94972 KiB

scrivener

#pragma once
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

const int NMAX = 1e6;
const int LGMAX = 21;

vector< vector<int> > father;
vector<int> lvl;
vector<int> active_node;
vector<char> c;

int create_new_node(int tata,char l){
    int node = (int)father.size();
    father.push_back(vector<int>(LGMAX,0));
    c.push_back(l);
    
    father.back()[0] = tata;
    lvl.push_back(1 + lvl[tata]);

    for(int i = 1;i < LGMAX;i++){
        father.back()[i] = father[father.back()[i - 1]][i - 1];
    }

    return node;
}

void Init() {
    father.push_back(vector<int>(LGMAX,0));
    active_node.push_back(0);
    lvl.push_back(0);
    c.push_back('0');
}

void TypeLetter(char L) {
    active_node.push_back(create_new_node(active_node.back(),L));
}

void UndoCommands(int U) {
    active_node.push_back(active_node[(int)active_node.size() - 1 - U]); 
}

char GetLetter(int P) {
    P++;
    int node = active_node.back();
    P = lvl[node] - P;

    for(int i = LGMAX - 1;i >= 0;i--){
        if((P >> i) & 1){
            node = father[node][i];
            P ^= (1 << i);
        }
    }

    return c[node];
}

Compilation message (stderr)

scrivener.cpp:1:9: warning: #pragma once in main file
 #pragma once
         ^~~~

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