#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define mid (l+r)/2
#define endl '\n'
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 1000010
#define MAXL 22
int trie[MAXN][27], anc[MAXN][MAXL], dub[MAXN];
vector<int> op;
int timer = 0;
void Init() {
timer = 1;
op.pb(1);
}
void TypeLetter(char L) {
int c = L-'a'+1, cur = op.back();
if(trie[cur][c] == 0) {
trie[cur][c] = ++timer;
anc[timer][0] = cur;
dub[timer] = dub[cur] + 1;
for(int i = 1; i < MAXL; i++) anc[timer][i] = anc[anc[timer][i-1]][i-1];
}
op.pb(trie[cur][c]);
}
void UndoCommands(int U) {
op.pb(op[sz(op)-1-U]);
}
char GetLetter(int P) {
int cur = op.back();
P = dub[cur] - 1 - P;
for(int k = MAXL-1; k >= 0; k--) {
if((1<<k) <= P) {
cur = anc[cur][k];
P -= (1<<k);
}
}
int par = anc[cur][0];
for(int i = 1; i < 27; i++) {
if(trie[par][i] == cur) return ('a'+i-1);
}
}
Compilation message
scrivener.cpp: In function 'char GetLetter(int)':
scrivener.cpp:56:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 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 |
4 ms |
760 KB |
Output is correct |
4 |
Correct |
4 ms |
988 KB |
Output is correct |
5 |
Correct |
3 ms |
760 KB |
Output is correct |
6 |
Correct |
4 ms |
1144 KB |
Output is correct |
7 |
Correct |
4 ms |
1144 KB |
Output is correct |
8 |
Correct |
4 ms |
888 KB |
Output is correct |
9 |
Correct |
4 ms |
1016 KB |
Output is correct |
10 |
Correct |
3 ms |
632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
620 ms |
119596 KB |
Output is correct |
2 |
Correct |
695 ms |
131464 KB |
Output is correct |
3 |
Correct |
493 ms |
128392 KB |
Output is correct |
4 |
Correct |
490 ms |
98864 KB |
Output is correct |
5 |
Correct |
654 ms |
111732 KB |
Output is correct |
6 |
Correct |
509 ms |
141668 KB |
Output is correct |
7 |
Correct |
562 ms |
71112 KB |
Output is correct |
8 |
Correct |
563 ms |
106532 KB |
Output is correct |
9 |
Correct |
734 ms |
145504 KB |
Output is correct |
10 |
Correct |
320 ms |
106720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
752 ms |
102676 KB |
Output is correct |
2 |
Correct |
869 ms |
91488 KB |
Output is correct |
3 |
Correct |
509 ms |
98488 KB |
Output is correct |
4 |
Correct |
478 ms |
72732 KB |
Output is correct |
5 |
Correct |
644 ms |
108564 KB |
Output is correct |
6 |
Correct |
533 ms |
101244 KB |
Output is correct |
7 |
Correct |
536 ms |
108356 KB |
Output is correct |
8 |
Correct |
635 ms |
53612 KB |
Output is correct |
9 |
Correct |
883 ms |
94696 KB |
Output is correct |
10 |
Correct |
305 ms |
106028 KB |
Output is correct |