Submission #751982

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
751982	2023-06-02T03:02:38 Z	minhcool	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	790 ms	88628 KB

scrivener

#include <bits/stdc++.h>
using namespace std;
 
int jump[(int)1e6+2][21];
char ch[(int)1e6+2];
int op = 0;
int dist[(int)1e6+2];
 
void Init(){
	for (int i=0; i<21; i++) jump[0][i] = 0;
	dist[0] = 0;
}
 
void TypeLetter(char L){
	op++;
	ch[op] = L;
	jump[op][0] = op-1;
	dist[op] = dist[op-1] + 1;
	for (int i=1; i<21; i++){
		jump[op][i] = jump[jump[op][i-1]][i-1];
	}
}
 
void UndoCommands(int U){
	op++;
	ch[op] = ch[op-U-1];
	jump[op][0] = jump[op-U-1][0];
	dist[op] = dist[op-U-1];
	for (int i=1; i<21; i++){
		jump[op][i] = jump[jump[op][i-1]][i-1];
	}
}
 
char GetLetter(int P){
	int d = dist[op] - P -1; 
	if (!d) return ch[op];
	int s = op;
	for (int i=0; i<21; i++){
		if (d & (1<<i)) s = jump[s][i];
	}
	return ch[s];
}

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	328 KB	Output is correct
4	Correct	1 ms	324 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	324 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	212 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	468 KB	Output is correct
2	Correct	2 ms	596 KB	Output is correct
3	Correct	2 ms	736 KB	Output is correct
4	Correct	2 ms	724 KB	Output is correct
5	Correct	3 ms	596 KB	Output is correct
6	Correct	3 ms	724 KB	Output is correct
7	Correct	2 ms	724 KB	Output is correct
8	Correct	2 ms	724 KB	Output is correct
9	Correct	2 ms	704 KB	Output is correct
10	Correct	2 ms	724 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	369 ms	62668 KB	Output is correct
2	Correct	419 ms	78688 KB	Output is correct
3	Correct	381 ms	77968 KB	Output is correct
4	Correct	438 ms	81620 KB	Output is correct
5	Correct	398 ms	72424 KB	Output is correct
6	Correct	339 ms	85088 KB	Output is correct
7	Correct	770 ms	73024 KB	Output is correct
8	Correct	723 ms	82228 KB	Output is correct
9	Correct	429 ms	78976 KB	Output is correct
10	Correct	314 ms	88628 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	463 ms	57548 KB	Output is correct
2	Correct	455 ms	51780 KB	Output is correct
3	Correct	366 ms	65336 KB	Output is correct
4	Correct	379 ms	56996 KB	Output is correct
5	Correct	354 ms	75696 KB	Output is correct
6	Correct	394 ms	78308 KB	Output is correct
7	Correct	367 ms	78156 KB	Output is correct
8	Correct	790 ms	66024 KB	Output is correct
9	Correct	643 ms	63524 KB	Output is correct
10	Correct	300 ms	87684 KB	Output is correct