Submission #309266

#	Time	Username	Problem	Language	Result	Execution time	Memory
309266		quocnguyen1012	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	527 ms	68400 KiB

scrivener

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define ar array
#define eb emplace_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

const int maxn = 1e6 + 5;

int curnode = 0, node = 0, len = 0;
int par[maxn][22], pos[maxn], depth[maxn];
char val[maxn];

void Init(void) {

}

void TypeLetter(char L) {
  ++node;
  ++len;

  depth[node] = depth[curnode] + 1;
  par[node][0] = curnode;
  curnode = node;
  pos[len] = curnode;
  val[node] = L;

  for (int i = 1; i < 22; ++i) {
    par[node][i] = par[par[node][i - 1]][i - 1];
  }
}

void UndoCommands(int U) {
  curnode = pos[len - U];
  ++len;
  pos[len] = curnode;
}

char GetLetter(int P) {
  int go = depth[curnode] - P - 1;
  int u = curnode;
  for (int i = 0; i < 22; ++i) {
    if (go >> i & 1) {
      u = par[u][i];
    }
  }
  return val[u];
}

#ifdef LOCAL
signed main(void) {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
  freopen("A.INP", "r", stdin);
  freopen("A.OUT", "w", stdout);
#endif // LOCAL
  int m;
  cin >> m;
  while (m--) {
    int op;
    cin >> op;
    if (op == 1) {
      char L;
      cin >> L;
      TypeLetter(L);
    } else if (op == 2) {
      int u;
      cin >> u;
      UndoCommands(u);
    } else {
      int k;
      cin >> k;
      cout << GetLetter(k) << '\n';
    }
  }
}
#endif // LOCAL

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