Submission #752056

#	Time	Username	Problem	Language	Result	Execution time	Memory
752056		LCJLY	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	469 ms	93004 KiB

scrivener

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 1000005;
int par[MAXN][20];
int idx[MAXN];
int l;
char val[MAXN];
int depth[MAXN];
void Init() {
  reach
  memset(par,-1,sizeof par);
}

void TypeLetter(char ch) {
  l++;
  idx[l]=l;
  val[l]=ch;
  par[l][0]=idx[l-1];
  depth[l] = depth[par[l][0]] + 1;
  FOR(i,1,19) {
    if(par[l][i-1] == -1)continue;
    par[l][i]=par[par[l][i-1]][i-1];
  }
}

void UndoCommands(int U) {
  ++l;
  idx[l]=idx[l-U-1];
}

char GetLetter(int P) {
  int depthdif=depth[idx[l]] - P - 1;
  int x=idx[l];
  FOR(i,0,19) {
    if(depthdif&(1<<i)) {
      x=par[x][i];
    }
  }
  return val[x];

}
#ifdef LOCAL
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16




int main() {
  int tmp;

  /* Set input and output buffering */
  char *inbuf, *outbuf;
  inbuf = (char*) malloc(inbuf_len * sizeof(char));
  outbuf = (char*) malloc(outbuf_len * sizeof(char));
  tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
  tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);

  Init();

  int cmd_num;
  tmp = scanf("%d", &cmd_num);
  assert(tmp == 1);

  int i;
  for (i = 0; i < cmd_num; i++) {
    char cmd;
    tmp = scanf(" %c", &cmd);
    assert(tmp == 1);
    if (cmd == 'T') {
      char letter;
      tmp = scanf(" %c", &letter);
      assert(tmp == 1);
      TypeLetter(letter);
    }
    else if (cmd == 'U') {
      int number;
      tmp = scanf("%d", &number);
      assert(tmp == 1);
      UndoCommands(number);
    }
    else if (cmd == 'P') {
      int index;
      char letter;
      tmp = scanf("%d", &index);
      assert(tmp == 1);
      letter = GetLetter(index);
      printf("%c\n", letter);
    }
  }

  return 0;

}
#endif

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