Submission #120757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
120757	2019-06-25T11:44:54 Z	MAMBA	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	872 ms	172280 KB

scrivener

#include <bits/stdc++.h>

using namespace std;

#define rep(i, j, k) for (int i = j; i < int(k); i++)

constexpr int N = 1e6 + 10;

struct node {
  node* par[20];
  char c = '\0';
  int deep = -1;
  node() { fill(par, par + 20, this); }
  node(char c_, node* p) {
    par[0] = p, c = c_;
    deep = p->deep + 1;
    rep(i, 1, 20) par[i] = par[i - 1]->par[i - 1];
  }
} state[N];

int now;
void Init() { now = 0; }

void TypeLetter(char L) {
  now++;
  state[now] = node(L, &state[now - 1]);
}

void UndoCommands(int U) {
  now++;
  state[now] = state[now - U - 1];
}

char GetLetter(int P) {
  int goUp = state[now].deep - P;
  node* me = &state[now];
  rep(i, 0, 20) if (goUp >> i & 1) me = me->par[i];
  return me->c;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	164728 KB	Output is correct
2	Correct	200 ms	164856 KB	Output is correct
3	Correct	120 ms	164728 KB	Output is correct
4	Correct	124 ms	164712 KB	Output is correct
5	Correct	124 ms	164744 KB	Output is correct
6	Correct	121 ms	164716 KB	Output is correct
7	Correct	122 ms	164676 KB	Output is correct
8	Correct	122 ms	164664 KB	Output is correct
9	Correct	121 ms	164720 KB	Output is correct
10	Correct	156 ms	164768 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	117 ms	164728 KB	Output is correct
2	Correct	120 ms	164736 KB	Output is correct
3	Correct	124 ms	164772 KB	Output is correct
4	Correct	120 ms	164728 KB	Output is correct
5	Correct	122 ms	164692 KB	Output is correct
6	Correct	119 ms	164728 KB	Output is correct
7	Correct	119 ms	164696 KB	Output is correct
8	Correct	119 ms	164728 KB	Output is correct
9	Correct	124 ms	164728 KB	Output is correct
10	Correct	123 ms	164772 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	121 ms	164728 KB	Output is correct
2	Correct	123 ms	164704 KB	Output is correct
3	Correct	124 ms	164684 KB	Output is correct
4	Correct	123 ms	164728 KB	Output is correct
5	Correct	125 ms	164728 KB	Output is correct
6	Correct	124 ms	164724 KB	Output is correct
7	Correct	123 ms	164728 KB	Output is correct
8	Correct	123 ms	164728 KB	Output is correct
9	Correct	120 ms	164760 KB	Output is correct
10	Correct	116 ms	164728 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	707 ms	168432 KB	Output is correct
2	Correct	761 ms	168952 KB	Output is correct
3	Correct	482 ms	169720 KB	Output is correct
4	Correct	488 ms	171104 KB	Output is correct
5	Correct	625 ms	169944 KB	Output is correct
6	Correct	598 ms	169056 KB	Output is correct
7	Correct	732 ms	171128 KB	Output is correct
8	Correct	788 ms	170232 KB	Output is correct
9	Correct	868 ms	169464 KB	Output is correct
10	Correct	278 ms	168872 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	785 ms	169484 KB	Output is correct
2	Correct	814 ms	171000 KB	Output is correct
3	Correct	488 ms	170616 KB	Output is correct
4	Correct	507 ms	172280 KB	Output is correct
5	Correct	576 ms	169796 KB	Output is correct
6	Correct	519 ms	169628 KB	Output is correct
7	Correct	525 ms	169616 KB	Output is correct
8	Correct	773 ms	171384 KB	Output is correct
9	Correct	872 ms	170968 KB	Output is correct
10	Correct	290 ms	168828 KB	Output is correct