# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1185030 | starnightsnow | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2000005;
vector<char> v;
vector<int> parent;
vector<int> sz;
vector<int> mp;
int cur = 0;
void Init() {
v.assign(1, 0);
parent.assign(1, -1);
sz.assign(1, 0);
mp.assign(1, 0);
cur = 0;
}
void TypeLetter(char L) {
int new_version = v.size();
v.push_back(L);
parent.push_back(cur);
sz.push_back(sz[cur] + 1);
mp.push_back(new_version);
cur = new_version;
}
void UndoCommands(int U) {
int undo = mp[mp.size() - 1 - U];
mp.push_back(undo);
cur = undo;
}
char GetLetter(int P) {
int v = cur;
int need = sz[v] - 1 - P;
while (v != 0) {
if (need == 0)
return v[v];
v = parent[v];
need--;
}
return ' ';
}