# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1004578 | Ausp3x | Crayfish scrivener (IOI12_scrivener) | C++17 | 1070 ms | 60960 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 人外有人,天外有天
// author: Ausp3x
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
typedef long long lng;
typedef unsigned int uint;
typedef unsigned long long ulng;
using namespace std;
using namespace __gnu_pbds;
int const INF32 = 0x3f3f3f3f;
lng const INF64 = 0x3f3f3f3f3f3f3f3f;
unordered_map<lng, vector<lng>> Trie;
vector<lng> history(1, -1);
int getLen(lng c) {
int len = 0;
while (c != -1) {
len += 1 << Trie[c].size() - 1;
c = Trie[c][Trie[c].size() - 1];
}
return len;
}
lng queryUp(lng c, int q) {
int i = 0;
while (q > 0) {
if (i >= Trie[c].size())
return -INF64;
if (q & 1)
c = Trie[c][i];
i++;
q >>= 1;
}
return c;
}
void debug() {
cout << endl;
cout << "Trie: " << endl;
for (auto [k, v] : Trie) {
cout << k << ": ";
for (lng x : v)
cout << x << ' ';
cout << endl;
}
cout << endl;
cout << "history: " << endl;
for (lng x : history)
cout << x << ' ';
cout << endl;
cout << endl;
return;
}
void Init() {
Trie[-1];
return;
}
void TypeLetter(char l) {
lng prv = history.back(), p_lv = (prv != -1 ? abs(prv) % 100000000 / 26 : -1);
lng cur = pow(-1, prv == -1) * (abs(prv) % 100000000 * 100000000 + (p_lv + 1) * 26 + (l - 'a'));
if (Trie[cur].size() == 0) {
Trie[cur].push_back(prv);
for (int i = 1; i < 20; i++) {
if (queryUp(prv, (1 << i) - 1) == -INF64)
break;
Trie[cur].push_back(queryUp(prv, (1 << i) - 1));
}
}
history.push_back(cur);
return;
}
void UndoCommands(int u) {
history.push_back(history[history.size() - u - 1]);
return;
}
char GetLetter(int p) {
int len = getLen(history.back());
return 'a' + (abs(queryUp(history.back(), len - p - 1)) % 100000000 % 26);
}
/*
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
Init();
TypeLetter('a');
TypeLetter('b');
cout << GetLetter(0) << endl;
cout << GetLetter(1) << endl;
UndoCommands(2);
TypeLetter('a');
TypeLetter('b');
cout << GetLetter(0) << endl;
cout << GetLetter(1) << endl;
UndoCommands(2);
UndoCommands(3);
TypeLetter('a');
TypeLetter('b');
cout << GetLetter(0) << endl;
cout << GetLetter(1) << endl;
UndoCommands(2);
TypeLetter('b');
TypeLetter('b');
cout << GetLetter(0) << endl;
cout << GetLetter(1) << endl;
debug();
// Init();
// TypeLetter('a');
// TypeLetter('b');
// cout << GetLetter(1) << endl;
// TypeLetter('d');
// UndoCommands(2);
// UndoCommands(1);
// cout << GetLetter(2) << endl;
// TypeLetter('e');
// UndoCommands(1);
// UndoCommands(5);
// TypeLetter('c');
// cout << GetLetter(2) << endl;
// UndoCommands(2);
// cout << GetLetter(2) << endl;
return 0;
}
//*/
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |