Submission #713481

#	Time	Username	Problem	Language	Result	Execution time	Memory
713481		hkoi	Crayfish scrivener (IOI12_scrivener)	C++17	5 / 100	274 ms	51636 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int mxN = 1000005;
char s[mxN];
int bin[20][mxN], depth[mxN], it = 1;
vector<int> tail = {0};
void Init() {
    
}
void TypeLetter(char c) {
    s[++it] = c;
    depth[it] = depth[tail.back()] + 1;
    bin[0][it] = tail.back();
    for (int i = 1; i < 20; i++) {
        bin[i][it] = bin[i-1][bin[i-1][it]];
    }
    tail.push_back(it);
}
void UndoCommands(int k) {
    tail.push_back(tail[tail.size()-k-1]);
}
char GetLetter(int k) {
    int ret = tail.back();
    for (int i = 0; i < 20; i++) {
        if ((1 << i) & depth[tail.back()-k-1]) ret = bin[i][ret];
    }
    return s[ret];
}

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