Submission #104265

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
104265	2019-04-04T14:14:37 Z	arman_ferdous	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	713 ms	86116 KB

scrivener

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

const int N = 1e6+10;
char c[N];
int lev[N];
int cur, freePtr;
int p[20][N], state[N], ptr;

void Init() {
	lev[0] = -1;
	memset(p,-1,sizeof p);
	c[0] = '?';
	cur = 0; freePtr = 1;
	state[0] = cur; ptr = 0;
}

void TypeLetter(char L) {
	int idx = freePtr++;
	p[0][idx] = cur;
	c[idx] = L, lev[idx] = lev[cur] + 1;
	cur = idx;

	for(int j = 1; j < 20; ++j)
		if(p[j-1][cur] + 1)
			p[j][cur] = p[j-1][p[j-1][cur]];
	state[++ptr] = cur;
}

void UndoCommands(int U) {
	state[ptr+1] = state[max(0, ptr - U)];
	ptr++;
	cur = state[ptr];
}

char GetLetter(int P) {
	int tmp = cur, need = lev[cur] - P;
	for(int j = 19; j >= 0; --j)
		if(need >= (1<<j)) {
			need -= (1<<j);
			tmp = p[j][tmp];
		}
	return c[tmp];
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	71 ms	78584 KB	Output is correct
2	Correct	67 ms	78628 KB	Output is correct
3	Correct	66 ms	78632 KB	Output is correct
4	Correct	70 ms	78584 KB	Output is correct
5	Correct	68 ms	78584 KB	Output is correct
6	Correct	71 ms	78584 KB	Output is correct
7	Correct	66 ms	78584 KB	Output is correct
8	Correct	68 ms	78584 KB	Output is correct
9	Correct	70 ms	78584 KB	Output is correct
10	Correct	73 ms	78712 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	69 ms	78576 KB	Output is correct
2	Correct	69 ms	78604 KB	Output is correct
3	Correct	76 ms	78584 KB	Output is correct
4	Correct	72 ms	78584 KB	Output is correct
5	Correct	70 ms	78584 KB	Output is correct
6	Correct	71 ms	78584 KB	Output is correct
7	Correct	67 ms	78584 KB	Output is correct
8	Correct	67 ms	78612 KB	Output is correct
9	Correct	66 ms	78712 KB	Output is correct
10	Correct	75 ms	78712 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	79 ms	78624 KB	Output is correct
2	Correct	65 ms	78648 KB	Output is correct
3	Correct	77 ms	78712 KB	Output is correct
4	Correct	79 ms	78624 KB	Output is correct
5	Correct	78 ms	78712 KB	Output is correct
6	Correct	78 ms	78712 KB	Output is correct
7	Correct	67 ms	78712 KB	Output is correct
8	Correct	69 ms	78712 KB	Output is correct
9	Correct	73 ms	78712 KB	Output is correct
10	Correct	71 ms	78712 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	443 ms	84588 KB	Output is correct
2	Correct	513 ms	85212 KB	Output is correct
3	Correct	427 ms	85316 KB	Output is correct
4	Correct	481 ms	84856 KB	Output is correct
5	Correct	473 ms	84996 KB	Output is correct
6	Correct	351 ms	86116 KB	Output is correct
7	Correct	442 ms	83832 KB	Output is correct
8	Correct	426 ms	84952 KB	Output is correct
9	Correct	470 ms	85868 KB	Output is correct
10	Correct	275 ms	85076 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	640 ms	84064 KB	Output is correct
2	Correct	713 ms	83968 KB	Output is correct
3	Correct	489 ms	84216 KB	Output is correct
4	Correct	455 ms	83576 KB	Output is correct
5	Correct	358 ms	84984 KB	Output is correct
6	Correct	391 ms	84728 KB	Output is correct
7	Correct	388 ms	84984 KB	Output is correct
8	Correct	576 ms	83344 KB	Output is correct
9	Correct	703 ms	84272 KB	Output is correct
10	Correct	269 ms	85080 KB	Output is correct