# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
970978 | asdasdqwer | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#include "scrivener.h"
vector<vector<int>> child;
int actNode;
int actSize;
int lft[1'000'000][21];
char last[1'000'000];
int cnt[1'000'000];
void calcJmp(int node) {
for (int j=1;j<21;j++) {
lft[node][j] = lft[node][j-1];
if (lft[node][j] != -1) {
lft[node][j] = lft[lft[node][j]][j-1];
}
if (lft[node][j] == -1) {
break;
}
}
}
void Init() {
actNode = 0;
actSize = 0;
child.push_back({});
for (int i=0;i<21;i++) {
lft[0][i] = -1;
}
}
void append() {
// append as child of actNode
actSize++;
child[actNode].push_back(actSize);
child.push_back({});
lft[actSize][0] = actNode;
last[actSize] = last[actNode];
cnt[actSize] = cnt[actNode];
calcJmp(actSize);
actNode = actSize;
}
void TypeLetter(char L) {
append();
last[actNode] = L;
cnt[actNode]++;
}
void UndoCommands(int U) {
actNode = actSize - U;
append();
}
char GetLetter(int P) {
int pt = actNode;
for (int i=20;i>=0;i--) {
if (lft[pt][i] != -1 && cnt[lft[pt][i]] > P) {
pt = lft[pt][i];
}
}
return last[pt];
}