제출 #195692

#제출 시각아이디문제언어결과실행 시간메모리
195692FieryPhoenix크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++11
34 / 100
1049 ms133296 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]; vector<int> anc[1000001]; bool started=false; int LOG[1000001]; void calcAnc(int ind){ for (int i=1;i<=LOG[length[ind]]+1;i++){ if (anc[ind][i-1]==-1 || i-1>=(int)anc[anc[ind][i-1]].size()) anc[ind].push_back(-1); else anc[ind].push_back(anc[anc[ind][i-1]][i-1]); } } void Init(){ anc[0].push_back(-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[nex-1]+1; c[nex]=ch; anc[nex].push_back(nex-1); calcAnc(nex); nex++; } void UndoCommands(int x){ length[nex]=length[nex-x-1]; c[nex]=c[nex-x-1]; anc[nex].push_back(anc[nex-x-1][0]); calcAnc(nex); nex++; } char GetLetter(int ind){ ind=length[nex-1]-1-ind; int cur=nex-1; for (int i=(int)anc[cur].size()-1;i>=0;i--){ if (((1<<i)&ind)!=0) cur=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...