Submission #418351

#TimeUsernameProblemLanguageResultExecution timeMemory
418351Aldas25Crayfish scrivener (IOI12_scrivener)C++14
100 / 100
549 ms151488 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define REP(n) FOR(O, 1, (n)) #define f first #define s second #define pb push_back typedef pair<int, int> pii; const int MAXK = 25; const int MAXN = 1e6+100; int cnt = 0; int ch[MAXN][26]; char letter[MAXN]; int lift[MAXN][MAXK]; int dep[MAXN]; int initNode (char c) { letter[cnt] = c; FOR(i, 0, 25) ch[cnt][i] = -1; cnt++; return cnt-1; } void buildLift (int id) { FOR(i, 1, MAXK-1) lift[id][i] = lift[lift[id][i-1]][i-1]; } int addNode (int id, char c) { int letId = c-'a'; if (ch[id][letId] == -1) { int chId = initNode(c); ch[id][letId] = chId; lift[chId][0] = id; buildLift(chId); dep[chId] = dep[id]+1; } return ch[id][letId]; } int lft (int id, int d) { FOR(i, 0, MAXK-1) if (d & (1<<i)) id = lift[id][i]; return id; } int curId; int timeToNode [MAXN]; void Init() { curId = 0; timeToNode[curId] = initNode('a'); dep[curId] = -1; } void TypeLetter(char L) { timeToNode[curId+1] = addNode(timeToNode[curId], L); curId++; } void UndoCommands(int U) { timeToNode[curId+1] = timeToNode[curId-U]; curId++; //printCur(); } char GetLetter(int P) { int nodeId = lft (timeToNode[curId], dep[timeToNode[curId]]-P); return letter[nodeId]; }
#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...