# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
601850 | acatmeowmeow | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5, LG = 20;
int vertex = 0, cur_vertex = 0, depth[N], lift[N][LG + 5];
char mp[N];
vector<int> command;
void Init() {
mp[0] = '\0', command.push_back(0);
for (int i = 0; i <= LG; i++) lift[0][i] = 0;
}
void TypeLetter(char L) {
vertex++;
int u = cur_vertex, v = vertex;
mp[v] = L;
depth[v] = depth[u] + 1;
lift[v][0] = u;
for (int i = 1; i <= LG; i++) lift[v][i] = lift[lift[u][i - 1]][i - 1];
command.push_back(v);
cur_vertex = v;
}
void UndoCommands(int U) {
int sz = command.size() - 1;
cur_vertex = command[sz - U];
command.push_back(cur_vertex);
}
bool set_bit(int mask, int k) { return mask & (1ll << k); }
char GetLetter(int P) {
int u = cur_vertex, jump = depth[u] - P - 1;
for (int i = 0; i <= LG; i++) {
if (!set_bit(jump, i)) continue;
u = lift[u][i];
}
return mp[u];
}
/*signed main() {
Init();
while (true) {
int type;
cin >> type;
if (type == 1) {
char ch;
cin >> ch;
TypeLetter(ch);
} else if (type == 2) {
int u;
cin >> u;
UndoCommands(u);
} else if (type == 3){
int u;
cin >> u;
cout << GetLetter(u) << endl;
} else break;
}
return 0;
}*/