Submission #225710

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
225710	2020-04-21T11:31:48 Z	spdskatr	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	535 ms	74976 KB

scrivener

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>

using namespace std;

int cnt = 1, cur = 0, jp[1000005][21], depth[1000005];
struct node {
	char val;
	int par;
} tree[1000005];

vector<int> pos;

void Init() { /* lol who inits amirite */ }

void TypeLetter(char L) {
	tree[cnt] = { L, cur };
	jp[cnt][0] = cur;
	depth[cnt] = depth[cur] + 1;
	cur = cnt;
	for (int k = 1; k <= 20; k++) jp[cur][k] = jp[jp[cur][k-1]][k-1];
	pos.push_back(cur);
	cnt++;
}

void UndoCommands(int U) {
	int nd = pos[pos.size() - 1 - U];
	cur = nd;
	pos.push_back(cur);
}

char GetLetter(int P) {
	int x = depth[cur] - P - 1;
	int c = cur;
	for (int k = 20; k >= 0; k--) {
		if ((x >> k) & 1) c = jp[c][k];
	}
	return tree[c].val;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	4 ms	384 KB	Output is correct
7	Correct	4 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	4 ms	384 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	256 KB	Output is correct
2	Correct	4 ms	256 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	512 KB	Output is correct
2	Correct	6 ms	512 KB	Output is correct
3	Correct	6 ms	640 KB	Output is correct
4	Correct	6 ms	768 KB	Output is correct
5	Correct	6 ms	512 KB	Output is correct
6	Correct	6 ms	768 KB	Output is correct
7	Correct	6 ms	768 KB	Output is correct
8	Correct	6 ms	640 KB	Output is correct
9	Correct	6 ms	640 KB	Output is correct
10	Correct	6 ms	512 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	357 ms	61612 KB	Output is correct
2	Correct	395 ms	67812 KB	Output is correct
3	Correct	349 ms	67328 KB	Output is correct
4	Correct	360 ms	55904 KB	Output is correct
5	Correct	396 ms	59356 KB	Output is correct
6	Correct	320 ms	73312 KB	Output is correct
7	Correct	361 ms	39392 KB	Output is correct
8	Correct	346 ms	56032 KB	Output is correct
9	Correct	427 ms	74976 KB	Output is correct
10	Correct	260 ms	55652 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	473 ms	53812 KB	Output is correct
2	Correct	535 ms	48736 KB	Output is correct
3	Correct	393 ms	53332 KB	Output is correct
4	Correct	379 ms	42088 KB	Output is correct
5	Correct	307 ms	57060 KB	Output is correct
6	Correct	342 ms	53856 KB	Output is correct
7	Correct	346 ms	57316 KB	Output is correct
8	Correct	439 ms	30808 KB	Output is correct
9	Correct	506 ms	50400 KB	Output is correct
10	Correct	270 ms	55264 KB	Output is correct