Submission #7280

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
7280	2014-07-29T06:54:32 Z	kriii	Crayfish scrivener (IOI12_scrivener)	C++	100 / 100	612 ms	176648 KB

scrivener

#include <vector>
#include <map>
using namespace std;

map<char, int> trie[1000001]; int prv[1000001][20];
int node,now,time,hist[1000001],len[1000001]; char last[10000001];

void Init() {}

void TypeLetter(char L) {
	int &n = trie[now][L];
	if (n == 0){
		n = ++node;
		prv[n][0] = now;
		for (int i=1;i<20;i++){
			prv[n][i] = prv[prv[n][i-1]][i-1];
			if (!prv[n][i]) break;
		}
		len[n] = len[now] + 1;
		last[n] = L;
	}
	hist[++time] = now = n;
}

void UndoCommands(int U) {
	now = hist[time-U];
	hist[++time] = now;
}

char GetLetter(int P) {
	int x = now; P = len[x] - P - 1;
	for (int i=0;i<20;i++) if (P & (1 << i)) x = prv[x][i];
	return last[x];
}

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

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

Subtask #3

22.0 / 22.0

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

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	484 ms	170708 KB	Output is correct
2	Correct	536 ms	173348 KB	Output is correct
3	Correct	508 ms	172556 KB	Output is correct
4	Correct	476 ms	165032 KB	Output is correct
5	Correct	460 ms	168464 KB	Output is correct
6	Correct	404 ms	175724 KB	Output is correct
7	Correct	384 ms	158432 KB	Output is correct
8	Correct	420 ms	167012 KB	Output is correct
9	Correct	568 ms	176648 KB	Output is correct
10	Correct	272 ms	167408 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	528 ms	166484 KB	Output is correct
2	Correct	544 ms	163580 KB	Output is correct
3	Correct	436 ms	165296 KB	Output is correct
4	Correct	464 ms	158696 KB	Output is correct
5	Correct	376 ms	167804 KB	Output is correct
6	Correct	428 ms	165956 KB	Output is correct
7	Correct	420 ms	167672 KB	Output is correct
8	Correct	476 ms	154340 KB	Output is correct
9	Correct	612 ms	164240 KB	Output is correct
10	Correct	300 ms	167144 KB	Output is correct