| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 538808 | __Variatto | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int L=20, A=26, MAX=1e6+1;
struct st{
st *jump[L+1], *g[A];
int war, gle;
};
int licznik;
st *ope[MAX];
st *root=new st;
void Init(){
for(int i=0; i<A-1; i++)
root->g[i]=nullptr;
for(int i=0; i<L; i++)
root->jump[i]=root;
root->gle=-1;
ope[0]=root;
}
void dodaj(st *v, char c){
if(v->g[c-'a']==nullptr){
st *nowy=new st;
for(int i=0; i<A-1; i++)
nowy->g[i]=nullptr;
nowy->war=c-'a';
nowy->gle=v->gle+1;
nowy->jump[0]=v;
for(int i=1; i<=L; i++)
nowy->jump[i]=nowy->jump[i-1]->jump[i-1];
v->g[c-'a']=nowy;
}
}
void TypeLetter(char c){
licznik++;
st *akt=ope[licznik-1];
dodaj(akt, c);
akt=akt->g[c-'a'];
ope[licznik]=akt;
}
void UndoCommands(int x){
licznik++;
ope[licznik]=ope[licznik-x-1];
}
char GetLetter(int pos){
st *akt=ope[licznik];
//cout<<akt<<"\n";
int x=akt->gle-pos, l=0;
while(x){
if(x%2) akt=akt->jump[l];
x/=2, l++;
}
return char(akt->war+'a');
}
int main(){
Init();
while(true){
char c;
cin>>c;
if(c=='T'){
char x;
cin>>x;
TypeLetter(x);
}
else if(c=='U'){
int x;
cin>>x;
UndoCommands(x);
}
else{
int x;
cin>>x;
cout<<GetLetter(x)<<"\n";
}
}
}