제출 #1191991

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191991		LolkasMeep	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++20	74 / 100	570 ms	278620 KiB

scrivener

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

const int LOG2 = 20;

int idcount = 1;

struct Try;

unordered_map<int, Try*> mp;

struct Try{
    Try* parent = NULL;
    Try *children[26] = {NULL};
    int h;
    char chr;
    int id;

    Try *jump[LOG2] = {NULL};

    Try(char c, Try* p){
        parent = p;
        chr = c;
        if(p==NULL) h = 0;
        else h = parent->h+1;

        Try *now = this;
        for(int i = 0; i < LOG2; i++){
            if(i == 0) now = parent;
            else if(now == NULL) now = NULL;
            else now = now->jump[i-1];
            jump[i] = now;
        }
        mp[idcount] = this;
        id = idcount;
        idcount++; 
    }

    Try* add(char c){
        if(children[c-'a'] != NULL) return children[c-'a'];

        children[c-'a'] = new Try(c, this);

        return children[c-'a'];
    }

    char get(int j){
        Try *now = this;

        for(int i = LOG2; i >= 0; i--){
            // cout << j << '\n';
            if(1<<i > j) continue;
            j -= 1<<i;
            now = now->jump[i];
        }

        return now->chr;
    }
};

int i=1;
// Try *tries[1000005];
int tries[1000005];
void Init(){
    tries[0] = 0;
    mp[0] = NULL;
};
void TypeLetter(char L){
    tries[i]=(new Try(L, mp[tries[i-1]]))->id;
    i++;
}
void UndoCommands(int U){
    tries[i]=tries[i-U-1];
    i++;
}
char GetLetter(int P){
    // cout << mp[tries[i-1]] << '\n';
    return (mp[tries[i-1]])->get(mp[tries[i-1]]->h-P);
}

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