| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 189074 | AQT | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct node{
int p;
int len;
char c;
};
node arr[1000005];
int crnt = 0, idx = 0;
int tbl[20][1000005];
void Init(){
arr[0] = {-1, 0, ' '};
}
void add(int idx){
for(int d = 1; d<20; d++){
tbl[d][idx] = tbl[d-1][tbl[d-1][idx]];
}
}
void TypeLetter(char c){
arr[++idx] = {crnt, arr[crnt].len+1, c};
tbl[0][idx] = crnt;
add(idx);
crnt = idx;
}
void UndoCommands(int u){
int k = crnt;
while(u--){
crnt = arr[crnt].p;
}
arr[++idx] = arr[crnt];
arr[idx].p = k;
add(idx);
crnt = idx;
}
char GetLetter(int p){
int t = crnt;
p++;
for(int d = 19; d>=0; d--){
if(arr[tbl[d][t]].len >= p){
t = tbl[d][t];
}
}
return arr[t].c;
}
int main(){
Init();
TypeLetter('a');
TypeLetter('b');
cout << GetLetter(1) << endl;
TypeLetter('d');
UndoCommands(2);
UndoCommands(1);
cout << GetLetter(2) << endl;
TypeLetter('e');
UndoCommands(1);
UndoCommands(5);
TypeLetter('c');
cout << GetLetter(2) << endl;
UndoCommands(2);
cout << GetLetter(2) << endl;
}