Submission #270191

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
270191	2020-08-17T13:01:05 Z	Saboon	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	533 ms	85856 KB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;

int me, newint, a[maxn], command = 1;
int par[maxn][20], h[maxn];
char cp[maxn];

void Init(){
	me = 0;
	newint = 1;
	memset(par, -1, sizeof par);
}

void TypeLetter(char L){
	int now = newint++;
	a[command++] = now;
	par[now][0] = me, h[now] = h[me]+1;
	cp[now] = L;
	for (int i = 1; par[now][i-1] != -1 and i < 20; i++)
		par[now][i] = par[par[now][i-1]][i-1];
	me = now;
}

void UndoCommands(int U){
	assert(U < command);
	a[command] = a[command-U-1], me = a[command++];
}

char GetLetter(int P){
	int now = me;
	int up = h[now]-P-1;
	for (int i = 0; i < 20; i++)
		if (up & (1 << i))
			now = par[now][i];
	return cp[now];
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	78584 KB	Output is correct
2	Correct	42 ms	78636 KB	Output is correct
3	Correct	42 ms	78584 KB	Output is correct
4	Correct	41 ms	78592 KB	Output is correct
5	Correct	42 ms	78612 KB	Output is correct
6	Correct	42 ms	78584 KB	Output is correct
7	Correct	41 ms	78584 KB	Output is correct
8	Correct	45 ms	78584 KB	Output is correct
9	Correct	43 ms	78712 KB	Output is correct
10	Correct	41 ms	78712 KB	Output is correct

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	78584 KB	Output is correct
2	Correct	44 ms	78624 KB	Output is correct
3	Correct	47 ms	78584 KB	Output is correct
4	Correct	41 ms	78588 KB	Output is correct
5	Correct	43 ms	78616 KB	Output is correct
6	Correct	44 ms	78592 KB	Output is correct
7	Correct	49 ms	78584 KB	Output is correct
8	Correct	48 ms	78712 KB	Output is correct
9	Correct	43 ms	78584 KB	Output is correct
10	Correct	48 ms	78584 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	78584 KB	Output is correct
2	Correct	55 ms	78748 KB	Output is correct
3	Correct	57 ms	78776 KB	Output is correct
4	Correct	52 ms	78712 KB	Output is correct
5	Correct	49 ms	78712 KB	Output is correct
6	Correct	44 ms	78712 KB	Output is correct
7	Correct	43 ms	78712 KB	Output is correct
8	Correct	72 ms	78712 KB	Output is correct
9	Correct	53 ms	78712 KB	Output is correct
10	Correct	44 ms	78712 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	371 ms	84484 KB	Output is correct
2	Correct	533 ms	85316 KB	Output is correct
3	Correct	379 ms	85240 KB	Output is correct
4	Correct	433 ms	84824 KB	Output is correct
5	Correct	418 ms	84848 KB	Output is correct
6	Correct	328 ms	85856 KB	Output is correct
7	Correct	373 ms	83832 KB	Output is correct
8	Correct	527 ms	84968 KB	Output is correct
9	Correct	496 ms	85768 KB	Output is correct
10	Correct	270 ms	85056 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	435 ms	84112 KB	Output is correct
2	Correct	485 ms	83832 KB	Output is correct
3	Correct	350 ms	84372 KB	Output is correct
4	Correct	455 ms	83608 KB	Output is correct
5	Correct	321 ms	84904 KB	Output is correct
6	Correct	423 ms	84728 KB	Output is correct
7	Correct	303 ms	84864 KB	Output is correct
8	Correct	508 ms	83192 KB	Output is correct
9	Correct	528 ms	84180 KB	Output is correct
10	Correct	256 ms	84984 KB	Output is correct