제출 #1191059

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191059		lrnnz	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	100 / 100	561 ms	182680 KiB

scrivener

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
 
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define ll long long
#define ui uint64_t
#define ar array
#define us unordered_set
#define cont(set, element) ((set).find(element) != (set).end())
 
/********* DEBUG *********/
 
template <typename T>
void outvec(const vector<T>& Z){
    for (const T& x : Z)
    cout << x << ' ';
    cout << "\n";
}

void printVariable(const any& var) {
    if (!var.has_value()) {
        cout << "null";
        return;
    }

    if (var.type() == typeid(int)) {
        cout << any_cast<int>(var);
    } else if (var.type() == typeid(double)) {
        cout << any_cast<double>(var);
    } else if (var.type() == typeid(float)) {
        cout << any_cast<float>(var);
    } else if (var.type() == typeid(char)) {
        cout << any_cast<char>(var);
    } else if (var.type() == typeid(bool)) {
        cout << (any_cast<bool>(var) ? "true" : "false");
    } else if (var.type() == typeid(string)) {
        cout << any_cast<string>(var);
    } else if (var.type() == typeid(const char*)) {
        cout << any_cast<const char*>(var);
    } else if (var.type() == typeid(long long)) {
        cout << any_cast<long long>(var);
    } else {
        cout << "[unknown type]";
    }
}

template<typename... Args>
void outval(Args... args) {
    vector<any> variables = {args...};
    
    for (size_t i = 0; i < variables.size(); ++i) {
        printVariable(variables[i]);
        if (i != variables.size() - 1) {
            cout << " ";
        }
    }
    cout << "\n";
}

#define nl "\n"
#define sp << " " <<

/********* DEBUG *********/

const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ll MOD3 = 1000000000;
const ll needMOD = 987654321; 
const ll mxN = 1000005;
const ll inf = 1e18; 

/*
    create trie, for each letter create new node, for undo commands go back U states,
    for getletter find P'th ancestor of current node, do it quick using binlift
*/

ll curridx, depth[mxN], jump[mxN][21];
char chars[mxN];
vector<ll> state;

void Init(){
    memset(depth, 0, sizeof(depth));
    memset(jump, 0, sizeof(jump));
    memset(chars, 0, sizeof(chars));

    curridx = 0;
    state.pb(0);
}

void TypeLetter(char L){
    curridx++;

    chars[curridx] = L;
    ll currstate = state.back();
    depth[curridx] = depth[currstate] + 1;
    jump[curridx][0] = currstate;

    for (int i = 1; i <= 20; i++){
        jump[curridx][i] = jump[ jump[curridx][i-1] ][i-1];
    }

    state.pb(curridx);
}

void UndoCommands(int U){
    state.pb(state[sz(state)-U-1]);
}

char GetLetter(int P){
    ll currstate = state.back();
    ll steps = depth[currstate] - P - 1;
    //outval("steps:",steps);
    for (int i = 0; i < 21; i++){
        if (steps & (1 << i)){
            currstate = jump[currstate][i];
        }
    }

    return chars[currstate];
}

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