Submission #427638

#	Time	Username	Problem	Language	Result	Execution time	Memory
427638		MarcoMeijer	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	527 ms	67140 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ii> vii;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), e.end()

const int MX = 1e6+10;

int pre[MX][20];
int head[MX], len[MX], current=0, nxt=0;
char last[MX];
int command=0;

void Init() {
  current = nxt = 0;
  head[0] = nxt;
  len[0] = 0;
  RE(i,20) pre[0][i] = 0;
  nxt++;
}

void TypeLetter(char L) {
  len[nxt] = len[current] + 1;
  last[nxt] = L;
  int x = current;
  RE(i,20) {
    pre[nxt][i] = x;
    x = pre[x][i];
  }
  head[++command] = current = nxt++;
}

void UndoCommands(int U) {
  command++;
  head[command] = current = head[command - U - 1];
}

char GetLetter(int P) {
  int dx = len[current] - P - 1;
  int u = current;
  RE(i,20) if(dx&(1<<i)) u = pre[u][i];
  return last[u];
}

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