제출 #255670

#제출 시각아이디문제언어결과실행 시간메모리
255670Akashi크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++14
34 / 100
1100 ms130596 KiB
//#include "grader.h" #include <bits/stdc++.h> using namespace std; const int DIM = 1e6 + 5; pair <int, int> cur = {0, 0}; vector <vector <int>> tt; vector <vector <int>> pref; int nr1, nr2; char ch[DIM]; int le[DIM], le2[DIM], tang[DIM]; int p2[25]; void Init() { tt.emplace_back(); pref.emplace_back(); p2[0] = 1; for (int i = 1; i <= 20 ; ++i) p2[i] = p2[i - 1] * 2; } void TypeLetter(char L) { ++nr1; ++nr2; le[nr1] = le[cur.first] + 1; ch[nr1] = L; pref.emplace_back(); pref[nr1].push_back(cur.first); for (int k = 1; p2[k] < le[nr1] ; ++k) pref[nr1].push_back(pref[pref[nr1][k - 1]][k - 1]); le2[nr2] = le2[cur.second] + 1; tt.emplace_back(); tt[nr2].push_back(cur.second); for (int k = 1; p2[k] < le2[nr2] ; ++k) tt[nr2].push_back(tt[tt[nr2][k - 1]][k - 1]); cur = {nr1, nr2}; tang[nr2] = nr1; } void UndoCommands(int U) { ++nr2; pair <int, int> aux = cur; for (int k = 0; U > 0 ; ++k) { if (p2[k] & U) { cur.second = tt[cur.second][k]; U = U ^ p2[k]; } } cur = {tang[cur.second], nr2}; tang[nr2] = cur.first; le2[cur.second] = le2[aux.second] + 1; tt.emplace_back(); tt[cur.second].push_back(aux.second); for (int k = 1; p2[k] < le2[cur.second] ; ++k) tt[cur.second].push_back(tt[tt[cur.second][k - 1]][k - 1]); } char GetLetter(int P) { ++P; int dif = le[cur.first] - P; int ind = cur.first; for (int k = 0; dif > 0 ; ++k) { if (p2[k] & dif) { ind = pref[ind][k]; dif = dif ^ p2[k]; } } return ch[ind]; }
#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...