| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 130247 | 2019-07-14T11:48:05 Z | khulegub | Crayfish scrivener (IOI12_scrivener) | C++14 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#define pb push_back
#define xx first
#define yy second
#define mp make_pair
using namespace std;
/*
#############################################
# x X x _ P u $ $ y S l a y e r 6 9 _ x X x #
#############################################
*/
/*
Check array size
Check IO
*/
int curr;
vector<pair<char, int> > s; //storing chars and ranks
// vector<int> node_par; //storing each node's origin
int node_par[100005][20]; //nodes parents
int par[100005][20]; //cmds parents
// vector<int> node_par[20];
// // vector<int> par; //storing each cmd's origin
// vector<int> par[20]; //bin uplifting
vector<int> pos; //storing each cmd's position in "s"
void Init() {
s.pb(mp('#', 0));
curr = 0; //current cmd is 0
pos.pb(0); //cmd 0 s position of node is 0
node_par[0][0] = 0;
par[0][0] = 0;
// node_par.pb(0);
// par.pb(0); //cmd zero came from zero lol
}
void TypeLetter(char L) {
par[curr + 1][0] = curr; //2 ^ 0 th parent
for (int i = 1; i <= 20; i++){
par[curr + 1][i] = par[ par[curr + 1][i - 1] ][i - 1];
}
s.pb(mp(L, s[ pos[curr] ].yy + 1)); //typing letter means new node
int node_curr = s.size() - 1;
node_par[node_curr][0] = pos[curr];
for (int i = 1; i <= 20; i++){
node_par[node_curr][i] = node_par[ node_par[node_curr][i - 1] ][i - 1];
}
pos.pb(s.size() - 1);
curr++;
}
void UndoCommands(int U) {
int origin = curr;
// need to uplift U times
for (int i = 0; i <= 20; i++){ // decompose U into binary
if ( (U & (1 << i)) ){
origin = par[origin][i];
}
}
par[curr + 1] = curr;
curr++;
pos.pb(pos[origin]);
}
char GetLetter(int P) {
P++;
int tmp = pos[curr];
int i = 0;
while( s[tmp].yy > P ){
tmp = node_par[tmp][i];
i++;
}
return s[tmp].xx;
}
// int main(){ //driver-chan
// Init();
// TypeLetter('a');
// cout << GetLetter(0);
// TypeLetter('b');
// cout << GetLetter(0);
// cout << GetLetter(1);
// UndoCommands(1);
// cout << GetLetter(0);
// TypeLetter('c');
// cout << GetLetter(1);
// // for (auto c : s){
// // cout << c.yy ;
// // }
// // cout << s.xx;
// }
/*
Atsaa hiiged bgan??
*/