# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
195117 | 2020-01-16T06:46:42 Z | FieryPhoenix | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++11 | 0 ms | 0 KB |
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include <cstdio> #include <map> #include <queue> #include <set> #include <iomanip> #include <deque> #include <cassert> #include <ctime> #include <cstring> #include <cstdlib> #include <chrono> #include <ctime> #include <random> #include <stack> #include <unordered_set> #include <unordered_map> #include <iterator> #include <climits> //#include "scrivener.h" using namespace std; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); typedef long long ll; typedef long double ld; #define INF 2001001001 #define MOD 1000000007 int nex; int length[1000001]; char c[1000001]; int anc[1000001][20]; bool started=false; void calcAnc(int ind){ for (int i=1;i<=19;i++){ if (anc[ind][i-1]==-1) anc[ind][i]=-1; else anc[ind][i]=anc[anc[ind][i-1]][i-1]; } } void Init(){ for (int i=0;i<20;i++) anc[0][i]=-1; } void TypeLetter(char ch){ if (!started){ root[0]=0; c[0]=ch; length[0]=1; nex++; started=true; return; } length[nex]=length[nex-1]+1; c[nex]=ch; anc[nex][0]=nex-1; calcAnc(nex); nex++; } void UndoCommands(int x){ length[nex]=length[nex-x]; c[nex]=c[nex-x]; anc[nex][0]=anc[nex-x][0]; calcAnc(nex); nex++; } char GetLetter(int ind){ ind=length[nex-1]-1-ind; int cur=nex-1; for (int i=19;i>=0;i--){ if (((1<<i)&ind)!=0) cur=anc[cur][i]; } return c[cur]; }