//# pragma GCC optimize("Ofast,no-stack-protector")
//# pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//# pragma GCC optimize("Ofast")
//# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
/*
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>
# include <ext/rope>
*/
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
//# define int ll
using namespace std;
char val[1 << 20];
int p[1 << 20][20];
vector<int>vec;
int curr,k;
int dep[1 << 20];
int nxt[1 << 20][26];
void Init()
{
vec.pb(0);
}
void TypeLetter(char L)
{
if(!nxt[curr][L - 'a'])
{
nxt[curr][L - 'a'] = ++k;
dep[k] = dep[curr] + 1;
val[k] = L;
p[k][0] = curr;
for(int i = 1;i <= 20;i++)
{
p[k][i] = p[p[k][i - 1]][i - 1];
}
curr = k;
}
else curr = nxt[curr][L - 'a'];
vec.pb(curr);
}
void UndoCommands(int U)
{
curr = vec[sz(vec) - U - 1];
vec.pb(curr);
}
char GetLetter(int P)
{
int y = dep[curr] - P - 1;
int x = curr;
for(int i = 0;i <= 20;i++)
{
if(y & (1 << i))
{
x = p[x][i];
}
}
return val[x];
}
Compilation message
scrivener.cpp: In function 'void TypeLetter(char)':
scrivener.cpp:47:12: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
p[k][i] = p[p[k][i - 1]][i - 1];
~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
scrivener.cpp:45:19: note: within this loop
for(int i = 1;i <= 20;i++)
~~^~~~~
# |
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 |
504 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 |
632 KB |
Output is correct |
3 |
Correct |
3 ms |
760 KB |
Output is correct |
4 |
Correct |
4 ms |
1016 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 |
1016 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 |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
679 ms |
109884 KB |
Output is correct |
2 |
Correct |
634 ms |
121012 KB |
Output is correct |
3 |
Correct |
463 ms |
117344 KB |
Output is correct |
4 |
Correct |
457 ms |
88148 KB |
Output is correct |
5 |
Correct |
517 ms |
101732 KB |
Output is correct |
6 |
Correct |
441 ms |
130600 KB |
Output is correct |
7 |
Correct |
438 ms |
62048 KB |
Output is correct |
8 |
Correct |
466 ms |
96248 KB |
Output is correct |
9 |
Correct |
694 ms |
133772 KB |
Output is correct |
10 |
Correct |
292 ms |
97636 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
581 ms |
93012 KB |
Output is correct |
2 |
Correct |
602 ms |
86896 KB |
Output is correct |
3 |
Correct |
459 ms |
93752 KB |
Output is correct |
4 |
Correct |
410 ms |
69208 KB |
Output is correct |
5 |
Correct |
419 ms |
103008 KB |
Output is correct |
6 |
Correct |
446 ms |
96144 KB |
Output is correct |
7 |
Correct |
439 ms |
102752 KB |
Output is correct |
8 |
Correct |
539 ms |
51140 KB |
Output is correct |
9 |
Correct |
701 ms |
89980 KB |
Output is correct |
10 |
Correct |
289 ms |
100576 KB |
Output is correct |