제출 #126221

#제출 시각아이디문제언어결과실행 시간메모리
126221groeneprof크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++14
60 / 100
1088 ms148936 KiB
#include <bits/stdc++.h> #define P(x) do {if(debug) cout << x << endl;} while(false) #define H(x) P(#x << ": " << x) #define FR(i, a, b) for(int i = (a); i < (b); ++i) #define F(i, n) FR(i, 0, n) using namespace std; const bool debug = 0; const int inf = 1e9; int N = 1000005; vector<int> ind; vector<char> parent; vector<int> depth; vector<vector<int> > memo; int cur; int root(int a){ if(a==ind[a]){ return a; } return ind[a] = root(ind[a]); } void print(){ if(debug){ cout<<"ind: "; F(i, cur+1) cout<<ind[i]<<" "; cout<<"\nparent: "; F(i, cur+1) cout<<parent[i]<<" "; cout<<"\ndepth: "; F(i, cur+1) cout<<depth[i]<<" "; cout<<"\nmemo: "; F(i, cur+1) cout<<memo[i][0]<<" "; } } int f(int i, int h){ if(memo[i][h]!=-1){ return memo[i][h]; } return memo[i][h] = f(f(i,h-1) , h-1); } void Init() { ind = {0}; parent = {'\\'}; depth = {0}; P("I"); memo.resize(N, vector<int> (23, -1)); memo[0][0] = 0; P("II"); cur = 0; } void TypeLetter(char L) { H(L); int n = cur+1; ind.push_back(n); parent.push_back(L); memo[n][0] = root(cur); depth.push_back(depth[root(cur)]+1); //cout<<endl; cur = n; } void UndoCommands(int U) { H(U); ind.push_back(cur-U); parent.push_back('/'); depth.push_back(-1); cur = cur+1; } char GetLetter(int P) { H(P); print(); int res = root(cur); for(int h = 22; h>=0; h--){ if(depth[root(f(res, h))]>P) res = f(res, h); } return parent[res]; }
#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...