/* Arthur Conmy / arthurconmy */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
#define REP(i,a,b) \
for(int i=(a); i<=(b); i++)
#define REPb(i,a,b) \
for(int i=(a); i>=(b); i--)
int p2[20];
int parent[20][1000001];
char letter_pres[1000001];
int cur_len[1000001];
int cur=0;
// vector<int> history;
void Init()
{
REP(i,0,19)
{
parent[0][i]=-1;
}
p2[0]=1;
REP(i,1,19)
{
p2[i]=p2[i-1]+p2[i-1];
}
}
void TypeLetter(char L)
{
parent[0][cur+1]=cur;
cur++;
letter_pres[cur]=L;
cur_len[cur]=cur_len[cur-1]+1;
REP(i,1,19)
{
parent[i][cur] = parent[i-1][parent[i-1][cur]];
}
}
void UndoCommands(int U)
{
int v_copying = cur - U;
cur++;
REP(i,0,19)
{
parent[i][cur] = parent[i][v_copying];
}
letter_pres[cur]=letter_pres[v_copying]; // could get iffy - unitialised char ???
cur_len[cur]=cur_len[v_copying];
}
char GetLetter(int P)
{
int length = cur_len[cur];
P++; // not zero-indexed anymore
int v=cur;
int up_trav = length-P;
REPb(i,19,0)
{
if(up_trav >= p2[i])
{
v=parent[i][v];
up_trav-=p2[i];
}
}
#ifdef ARTHUR_LOCAL
cout << letter_pres[v] << endl;
#endif
return letter_pres[v];
}
// int main()
// {
// #ifdef ARTHUR_LOCAL
// ifstream cin("input.txt");
// #endif
// Init();
// TypeLetter('a');
// TypeLetter('b');
// GetLetter(1);
// TypeLetter('d');
// UndoCommands(2);
// UndoCommands(1);
// GetLetter(2);
// TypeLetter('e');
// UndoCommands(1);
// UndoCommands(5);
// TypeLetter('c');
// GetLetter(2);
// UndoCommands(2);
// GetLetter(2);
// }
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
504 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
2 ms |
504 KB |
Output is correct |
7 |
Correct |
2 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
504 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
632 KB |
Output is correct |
2 |
Correct |
2 ms |
508 KB |
Output is correct |
3 |
Correct |
2 ms |
504 KB |
Output is correct |
4 |
Correct |
2 ms |
504 KB |
Output is correct |
5 |
Correct |
2 ms |
504 KB |
Output is correct |
6 |
Correct |
3 ms |
504 KB |
Output is correct |
7 |
Correct |
3 ms |
504 KB |
Output is correct |
8 |
Correct |
2 ms |
504 KB |
Output is correct |
9 |
Correct |
2 ms |
632 KB |
Output is correct |
10 |
Correct |
2 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
632 KB |
Output is correct |
2 |
Correct |
3 ms |
760 KB |
Output is correct |
3 |
Correct |
3 ms |
888 KB |
Output is correct |
4 |
Correct |
3 ms |
936 KB |
Output is correct |
5 |
Correct |
4 ms |
760 KB |
Output is correct |
6 |
Correct |
4 ms |
888 KB |
Output is correct |
7 |
Correct |
4 ms |
888 KB |
Output is correct |
8 |
Correct |
4 ms |
888 KB |
Output is correct |
9 |
Correct |
3 ms |
888 KB |
Output is correct |
10 |
Correct |
3 ms |
888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
323 ms |
63676 KB |
Output is correct |
2 |
Correct |
389 ms |
77216 KB |
Output is correct |
3 |
Correct |
425 ms |
77532 KB |
Output is correct |
4 |
Correct |
471 ms |
82240 KB |
Output is correct |
5 |
Correct |
424 ms |
72004 KB |
Output is correct |
6 |
Correct |
351 ms |
83448 KB |
Output is correct |
7 |
Correct |
557 ms |
73848 KB |
Output is correct |
8 |
Correct |
485 ms |
81872 KB |
Output is correct |
9 |
Correct |
406 ms |
78016 KB |
Output is correct |
10 |
Correct |
271 ms |
86792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
491 ms |
59844 KB |
Output is correct |
2 |
Correct |
551 ms |
52936 KB |
Output is correct |
3 |
Correct |
397 ms |
65912 KB |
Output is correct |
4 |
Correct |
430 ms |
59116 KB |
Output is correct |
5 |
Correct |
315 ms |
75000 KB |
Output is correct |
6 |
Correct |
337 ms |
77372 KB |
Output is correct |
7 |
Correct |
340 ms |
77304 KB |
Output is correct |
8 |
Correct |
733 ms |
67316 KB |
Output is correct |
9 |
Correct |
513 ms |
64488 KB |
Output is correct |
10 |
Correct |
250 ms |
85880 KB |
Output is correct |