Submission #1209161

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209161		LIA	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	1101 ms	215384 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, ll> plll;
typedef vector<plll> vplll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<vector<pll>> vvpll;
typedef vector<vector<ll>> vvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
const ll LOG = 20;
ll timer = 0;
struct Node { char c; ll idx_of_par; };
vector<Node> tr;
vll depth;
vector<vll> up;
vll ver;
ll cur;
void Init() {
  timer = 0;
  Node nd = {'%', timer++};
  tr.clear(); tr.push_back(nd);
  depth.clear(); depth.push_back(0);
  up.clear(); up.emplace_back(vll(LOG, 0));
  ver.clear();
  cur = 0;
}
void TypeLetter(char l) {
  ll v = timer++;
  tr.push_back({l, cur});
  depth.push_back(depth[cur] + 1);
  up.emplace_back(vll(LOG));
  up[v][0] = cur;
  loop(j, 1, LOG) up[v][j] = up[ up[v][j-1] ][j-1];
  cur = v;
  ver.push_back(cur);
}
void UndoCommands(int u) {
  ll target = ver[ver.size() - u - 1];
  ll v = timer++;
  tr.push_back({'%', target});
  depth.push_back(depth[target]);
  up.emplace_back(vll(LOG));
  up[v][0] = target;
  loop(j, 1, LOG) up[v][j] = up[ up[v][j-1] ][j-1];
  cur = v;
  ver.push_back(cur);
}
char GetLetter(int p) {
  ll target = p + 1;
  ll node = cur;
  loopr(j, LOG, 0) {
    ll anc = up[node][j];
    if (depth[anc] >= target) node = anc;
  }
  return tr[node].c;
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 0 / 26
• Subtask 5: 0 / 40