제출 #195703

#제출 시각아이디문제언어결과실행 시간메모리
195703FieryPhoenix크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++11
5 / 100
829 ms67808 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 LOG[1000001]; int point[1000001]; void calcAnc(int ind){ for (int i=1;i<=LOG[length[ind]];i++){ if (point[anc[ind][i-1]]==-1 || i-1>LOG[length[point[anc[ind][i-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; anc[0][0]=-1; for (int i=0;i<20;i++) LOG[1<<i]=i; for (int i=1;i<=1000000;i++) if (LOG[i]==0) LOG[i]=LOG[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-1]; nex++; } char GetLetter(int ind){ ind=length[nex-1]-1-ind; int cur=nex-1; cur=point[cur]; for (int i=LOG[length[point[cur]]];i>=0;i--){ if (((1<<i)&ind)!=0) cur=point[anc[cur][i]]; } return c[cur]; }
#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...