Submission #241598

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
241598	2020-06-24T16:42:44 Z	johutha	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	565 ms	90616 KB

scrivener

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

int upr[1000001][21];
char ch[1000001];
int len[1000001];
int cnt = 0;

void Init()
{
	cnt = 1;
	for (int i = 0; i < 21; i++) upr[0][i] = 0;
}

void TypeLetter(char L)
{
	ch[cnt] = L;
	len[cnt] = len[cnt - 1] + 1;
	upr[cnt][0] = cnt - 1;
	for (int i = 1; i < 21; i++) upr[cnt][i] = upr[upr[cnt][i - 1]][i - 1];
	cnt++;
}

void UndoCommands(signed U)
{
	int st = cnt - U - 1;
	ch[cnt] = ch[st];
	for (int i = 0; i < 21; i++) upr[cnt][i] = upr[st][i];
	len[cnt] = len[st];
	cnt++;
}

char GetLetter(signed P)
{
	int u = len[cnt - 1] - 1 - P;
	int c = cnt - 1;

	for (int i = 0; i < 21; i++)
	{
		if (u & (1<<i))
		{
			c = upr[c][i];
		}
	}
	return ch[c];
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 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	5 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	4 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct

Subtask #2

7.0 / 7.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	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 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 #3

22.0 / 22.0

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

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	391 ms	62840 KB	Output is correct
2	Correct	455 ms	76536 KB	Output is correct
3	Correct	418 ms	76024 KB	Output is correct
4	Correct	438 ms	79608 KB	Output is correct
5	Correct	495 ms	70392 KB	Output is correct
6	Correct	402 ms	82936 KB	Output is correct
7	Correct	480 ms	72312 KB	Output is correct
8	Correct	474 ms	85344 KB	Output is correct
9	Correct	498 ms	81528 KB	Output is correct
10	Correct	293 ms	90616 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	440 ms	57552 KB	Output is correct
2	Correct	494 ms	49656 KB	Output is correct
3	Correct	418 ms	63316 KB	Output is correct
4	Correct	451 ms	54776 KB	Output is correct
5	Correct	402 ms	73756 KB	Output is correct
6	Correct	407 ms	76152 KB	Output is correct
7	Correct	391 ms	76152 KB	Output is correct
8	Correct	565 ms	64888 KB	Output is correct
9	Correct	528 ms	67064 KB	Output is correct
10	Correct	300 ms	89592 KB	Output is correct