# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
108229 | 2019-04-28T10:02:52 Z | SecretAgent007 | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h> using namespace std; vector< vector< int > > parents(21, vector< int > (1000009,-1)); int curr = 0; vector< int > v(1000009); vector< int > depth(1000009); vector< char > letter(1000009); void Init(){ } void TypeLetter(char c){ curr++; v[curr] = curr; depth[curr] = depth[v[curr-1]]+1; letter[curr] = c; parents[0][curr] = v[curr-1]; for(int i = 1; i < 21; i++){ if(parents[i-1][curr] != -1){ parents[i][curr] = parents[i-1][parents[i-1][curr]]; } } } void UndoCommands(int n){ v[curr+1] = v[curr-n]; curr++; } char getLetter(int n){ int jump = depth[v[curr]]-n-1; int nb = v[curr]; for(int i = 0; i < 21; i++){ if((1<<i) & jump){ nb = parents[i][nb]; } } return letter[nb]; } /* signed main(){ ios::sync_with_stdio(false); cin.tie(0); char c; while(cin >> c){ if(c == 'T'){ char a; cin >> a; TypeLetter(a); }else if(c == 'G'){ int a; cin >> a; cout << getLetter(a) << endl; }else{ int a; cin >> a; UndoCommands(a); } } } */