Submission #1183514

#TimeUsernameProblemLanguageResultExecution timeMemory
1183514countlessCrayfish scrivener (IOI12_scrivener)C++20
12 / 100
1097 ms57720 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const ll MOD = 998244353; const ll INF = 1e18; const ld EPS = 1e-12; #define endl "\n" #define sp <<" "<< #define REP(i, a, b) for(ll i = a; i < b; i++) #define dbg(x) cout << #x << " = " << x << endl #define mp make_pair #define pb push_back #define fi first #define se second #define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL) #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) ((ll)(x).size()) struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template <typename Key, typename Value> using hash_map = unordered_map<Key, Value, custom_hash>; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); // uniform_int_distribution<int>(a, b)(rng); // shuffle(all(a), rng); const int MAXY = 26; int curr; string s; struct trie { int next[MAXY]; bool output = false; trie() { fill(begin(next), end(next), -1); } }; vector<trie> t(1); vector<int> up(1); void Init() { s = ""; curr = 0; // t[0].output = true; // up[0] = -1; } void TypeLetter(char L) { int x = L - 'a'; if (t[curr].next[x] == -1) { t[curr].next[x] = t.size(); t.emplace_back(); up.push_back(curr); // cerr << curr << endl; } curr = t[curr].next[x]; t[curr].output = true; } void UndoCommands(int U) { for (int i = 0; i < U; i++) { if (up[curr] == 0) break; t[curr].output = false; // cerr << curr sp t.size() sp up.size() sp up[curr] << endl; curr = up[curr]; } } char GetLetter(int P) { int timer = -1; int x = 0, out; while (timer != P) { for (int i = 0; i < MAXY; i++) { if (t[t[x].next[i]].output == true) { x = t[x].next[i]; out = i; timer++; break; } } } return out + 'a'; } // int main() { // Init(); // int n; cin >> n; // char command; // REP(i, 0, n) { // cin >> command; // if (command == 'T') { // char c; cin >> c; // TypeLetter(c); // } // else if (command == 'U') { // int x; cin >> x; // UndoCommands(x); // } // else { // int x; cin >> x; // cout << GetLetter(x) << endl; // } // } // }
#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...