제출 #195707

#제출 시각아이디문제언어결과실행 시간메모리
195707FieryPhoenix크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++11
100 / 100
929 ms90616 KiB
#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; int point[1000001]; 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]=point[anc[point[anc[ind][i-1]]][i-1]]; } } void Init(){ for (int i=0;i<=1000000;i++) point[i]=i; for (int i=0;i<20;i++) anc[0][i]=-1; } void TypeLetter(char ch){ if (!started){ c[0]=ch; length[0]=1; nex++; started=true; return; } length[nex]=length[point[nex-1]]+1; c[nex]=ch; anc[nex][0]=point[nex-1]; calcAnc(nex); nex++; } void UndoCommands(int x){ point[nex]=point[nex-x-1]; nex++; } char GetLetter(int ind){ ind=length[point[nex-1]]-1-ind; int cur=nex-1; cur=point[cur]; for (int i=19;i>=0;i--){ if (((1<<i)&ind)!=0) cur=point[anc[cur][i]]; } return c[cur]; } /* int main(){ Init(); for (;;){ char c; cin>>c; if (c=='T'){ char d; cin>>d; TypeLetter(d); } else if (c=='U'){ int x; cin>>x; UndoCommands(x); } else{ int x; cin>>x; cout<<GetLetter(x)<<endl; } } } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...