제출 #1229803

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1229803		AMel0n	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++20	0 / 100	558 ms	242844 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define FOR(i,N) for(ll i = 0; i < N; i++)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second


vector<int> cmd = {0};  // cmd[i] -> idx of cur node    after ith command (1-indexed)
vector<int> len = {0};  // len[i] -> len of cur string  after ith command (1-indexed)
vector<char> node; // node value
vector<vector<int>> par(2e6, vector<int>(20)); // node parent (binary jumping)
int n = 0; // nodes created

void Init() {}

void TypeLetter(char ch) {
    len.push_back(len[cmd.back()] + 1);
    par[n][0] = cmd.back();
    cmd.push_back(n);
    node.push_back(ch);
    for(int j = 1; j < 20; j++) par[n][j] = par[par[n][j-1]][j-1];
    n++;
}

void UndoCommands(int k) {
    cmd.push_back(cmd[cmd.size()-1-k]);
}

char GetLetter(int k) {
    k = k - len[cmd.back() + 1] - 1;
    int j = 19;
    int bru = cmd.back();
    while(j > -1) {
        if (pow(2, j) <= k) {
            bru = par[bru][j];
            k -= pow(2, j);
        }
        j--;
    }
    return node[bru];
}

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