Submission #130261

#TimeUsernameProblemLanguageResultExecution timeMemory
130261khulegubCrayfish scrivener (IOI12_scrivener)C++14
0 / 100
408 ms69444 KiB
#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[1000005][22]; //nodes parents int par[1000005][22]; //cmds parents // vector<int> node_par[22]; // // vector<int> par; //storing each cmd's origin // vector<int> par[22]; //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 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 <= 22; i++){ par[curr + 1][i] = par[ par[curr + 1][i - 1] ][i - 1]; if (par[curr + 1][i] == 0 ) break; } s.pb(mp(L, s[ pos[curr] ].yy + 1)); //typing letter means new node pos.pb(s.size() - 1); curr++; } void UndoCommands(int U) { int origin = curr; // need to uplift U times for (int i = 0; i <= 22; i++){ // decompose U into binary if ( (U & (1 << i)) ){ origin = par[origin][i]; } } par[curr + 1][0] = curr; //2 ^ 0 th parent for (int i = 1; i <= 22; i++){ par[curr + 1][i] = par[ par[curr + 1][i - 1] ][i - 1]; if (par[curr + 1][i] == 0 ) break; } curr++; pos.pb(pos[origin]); } char GetLetter(int P) { P++; int tmp = curr; for (int i = 22; i >= 0; i--){ if (s[pos[tmp]].yy > P) tmp = par[tmp][i]; } return s[pos[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?? */
#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...