Submission #7279

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
7279	2014-07-29T06:51:23 Z	kriii	Crayfish scrivener (IOI12_scrivener)	C++	100 / 100	604 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];
		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	12 ms	143780 KB	Output is correct
2	Correct	12 ms	143780 KB	Output is correct
3	Correct	4 ms	143912 KB	Output is correct
4	Correct	16 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	12 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 #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	4 ms	143780 KB	Output is correct
4	Correct	4 ms	143780 KB	Output is correct
5	Correct	8 ms	143780 KB	Output is correct
6	Correct	16 ms	143912 KB	Output is correct
7	Correct	8 ms	143780 KB	Output is correct
8	Correct	8 ms	143780 KB	Output is correct
9	Correct	4 ms	143912 KB	Output is correct
10	Correct	12 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	12 ms	143912 KB	Output is correct
4	Correct	12 ms	143912 KB	Output is correct
5	Correct	8 ms	143912 KB	Output is correct
6	Correct	8 ms	144044 KB	Output is correct
7	Correct	12 ms	144044 KB	Output is correct
8	Correct	8 ms	143912 KB	Output is correct
9	Correct	4 ms	143912 KB	Output is correct
10	Correct	8 ms	143912 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	512 ms	170708 KB	Output is correct
2	Correct	588 ms	173348 KB	Output is correct
3	Correct	520 ms	172556 KB	Output is correct
4	Correct	520 ms	165032 KB	Output is correct
5	Correct	480 ms	168464 KB	Output is correct
6	Correct	392 ms	175724 KB	Output is correct
7	Correct	380 ms	158432 KB	Output is correct
8	Correct	436 ms	167012 KB	Output is correct
9	Correct	604 ms	176648 KB	Output is correct
10	Correct	300 ms	167408 KB	Output is correct

Subtask #5

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	552 ms	166484 KB	Output is correct
2	Correct	548 ms	163580 KB	Output is correct
3	Correct	464 ms	165296 KB	Output is correct
4	Correct	468 ms	158696 KB	Output is correct
5	Correct	396 ms	167804 KB	Output is correct
6	Correct	392 ms	165956 KB	Output is correct
7	Correct	428 ms	167672 KB	Output is correct
8	Correct	488 ms	154340 KB	Output is correct
9	Correct	604 ms	164240 KB	Output is correct
10	Correct	332 ms	167144 KB	Output is correct