Submission #72963

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72963	2018-08-27T10:04:26 Z	Hoget157	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	1000 ms	70008 KB

scrivener

struct Node{
	public:
	int num,par[22] = {};
	char c;
};

int cnt;
Node *root,*p[1000010];

void Init() {
	cnt = 0;
	root = new Node;
	root->num = -1;
	p[cnt++] = root;
}

void TypeLetter(char L) {
	p[cnt] = new Node;
	p[cnt]->c = L;
	p[cnt]->par[0] = cnt - 1;
	p[cnt]->num = p[cnt - 1]->num + 1;
	for(int i = 1;i < 22;i++){
		if(p[cnt]->par[i - 1]) p[cnt]->par[i] = p[p[cnt]->par[i - 1]]->par[i - 1];
		else break;
	}
	cnt++;
}

void UndoCommands(int U) {
	p[cnt] = p[cnt - U - 1];
	cnt++;
}

char GetLetter(int P) {
	int tmp = cnt - 1;
	for(int i = 0;i < 22;i++){
		if(p[tmp]->num == P) break;
		if(((p[tmp]->num - P) >> i) & 1) tmp = p[tmp]->par[i];
	}
	return p[tmp]->c;
}

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

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

Subtask #3

22.0 / 22.0

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

Subtask #4

0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1002 ms	70008 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1020 ms	70008 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-