Submission #234549

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
234549	2020-05-24T12:53:56 Z	crossing0ver	Crayfish scrivener (IOI12_scrivener)	C++17	100 / 100	894 ms	86648 KB

scrivener

#include<bits/stdc++.h>
using namespace std;        
int operations;
char lastchar[1000005];
int P[1000005][20],sz[1000005];
void Init() {}    

void TypeLetter(char L){
	operations++;
	P[operations][0] = operations - 1;
	sz[operations] = sz[operations - 1] + 1;
	for (int i = 1; i < 20; i ++)
		P[operations][i] = P[ P[operations][i-1] ][i-1];
	lastchar[operations] = L;
}

void UndoCommands(int U) {
	operations++;
	sz[operations] = sz[operations - 1 - U];
	P[operations][0] = P[operations - 1 - U][0];
	lastchar[operations]= lastchar[operations - 1 - U];
	for (int i = 1; i < 20; i++)
		P[operations][i] = P[ P[operations][i-1] ][i-1];
}


char GetLetter(int p) {
	int x = sz[operations] - p - 1;
	int cur = operations;
	for (int i = 0; i < 20 ;i++) {
		if (x & (1 << i)) {
			cur = P[cur][i];
		}
	}
	return lastchar[cur];
}

Subtask #1

5.0 / 5.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	5 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	5 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	4 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	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	4 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	5 ms	384 KB	Output is correct
9	Correct	4 ms	384 KB	Output is correct
10	Correct	5 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	7 ms	768 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	411 ms	63624 KB	Output is correct
2	Correct	486 ms	77048 KB	Output is correct
3	Correct	419 ms	76536 KB	Output is correct
4	Correct	508 ms	80120 KB	Output is correct
5	Correct	436 ms	71184 KB	Output is correct
6	Correct	349 ms	83192 KB	Output is correct
7	Correct	894 ms	71928 KB	Output is correct
8	Correct	824 ms	80376 KB	Output is correct
9	Correct	471 ms	77432 KB	Output is correct
10	Correct	330 ms	86648 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	464 ms	58872 KB	Output is correct
2	Correct	494 ms	51584 KB	Output is correct
3	Correct	429 ms	64376 KB	Output is correct
4	Correct	476 ms	56508 KB	Output is correct
5	Correct	388 ms	74360 KB	Output is correct
6	Correct	424 ms	76828 KB	Output is correct
7	Correct	425 ms	76860 KB	Output is correct
8	Correct	893 ms	65228 KB	Output is correct
9	Correct	699 ms	62840 KB	Output is correct
10	Correct	335 ms	85624 KB	Output is correct