Submission #965947

#	Time	Username	Problem	Language	Result	Execution time	Memory
965947		hirayuu_oj	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	344 ms	141132 KiB

scrivener

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)

const int N=1000000;
vector<int> indexs;
int ver=1;
vector<array<int,32>> inf_stack(N);
vector<char> lets(N);
vector<int> lens(N);
void Init() {
    lets[0]=' ';
    lens[0]=0;
    rep(i,32)inf_stack[0][i]=0;
    indexs.push_back(0);
}

void TypeLetter(char L) {

    lets[ver]=L;
    lens[ver]=lens[indexs.back()]+1;
    inf_stack[ver][0]=indexs.back();
    indexs.push_back(ver);
    for(int i=1; i<32; i++){
        inf_stack[ver][i]=inf_stack[inf_stack[ver][i-1]][i-1];
    }
    ver++;

}

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

char GetLetter(int P) {

    int back=lens[indexs.back()]-P-1;
    int pos=indexs.back();
    rep(i,32){
        if(back&1){
            pos=inf_stack[pos][i];
        }
        back/=2;
    }

    return lets[pos];

}

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