Submission #1183562

#TimeUsernameProblemLanguageResultExecution timeMemory
1183562countlessCrayfish scrivener (IOI12_scrivener)C++20
12 / 100
1097 ms59264 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]; char c = '#'; bool output = false; trie() { fill(begin(next), end(next), -1); } }; vector<trie> t(1); vector<int> depth(1); vector<int> up(1); void Init() { s = ""; curr = 0; t[0].output = true; up[0] = -1; depth[0] = 0; } void TypeLetter(char L) { int x = L - 'a'; if (t[curr].next[x] == -1) { int ind = t.size(); depth[ind] = depth[curr] + 1; t[curr].next[x] = ind; t.emplace_back(); up.push_back(curr); depth.push_back(depth[curr]+1); t[ind].c = L; } 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 x = curr; while (depth[x]-1 != P) { x = up[x]; } return t[x].c; } // 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...