Submission #68080

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
68080	2018-08-15T21:31:44 Z	naderjemel	Crayfish scrivener (IOI12_scrivener)	C++14	60 / 100	1000 ms	158360 KB

scrivener

#include <bits/stdc++.h>
using namespace std;
const int LOG = 21;
struct node
{
	char c; int s;
	node *anc[LOG];
	node(){
		for(int i=0;i<LOG;i++) anc[i] = NULL;
		s=0;
	}
}*tree [1000005];

int id;
void Init(){
	id=1;
	tree[0] = new node();

}
void TypeLetter(char L) {
	int n=id++;
	tree[n] = new node();
	tree[n]->s = tree[n-1]->s+1;
	tree[n]->c = L;
	tree[n]->anc[0]=tree[n-1];
	for(int i=1;i<LOG;i++) tree[n]->anc[i] = (tree[n]->anc[i-1]) ? (tree[n]->anc[i-1])->anc[i-1] : NULL; 
}

void UndoCommands(int U) {
	int ret=id-1-U;
	int n=id++;
	tree[n]=tree[ret];
}


char GetLetter(int P) {
	int n=id-1;
	node *h = new node();
	h=tree[n];
	int up=tree[n]->s - 1 - P;
	for(int i=LOG-1;i>=0;i--){
		if(up - (1<<i) >= 0){
			up-=(1<<i);
			h=h->anc[i];
		}
	}
	return h->c;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 ms	356 KB	Output is correct
3	Correct	3 ms	392 KB	Output is correct
4	Correct	3 ms	468 KB	Output is correct
5	Correct	3 ms	544 KB	Output is correct
6	Correct	2 ms	544 KB	Output is correct
7	Correct	3 ms	544 KB	Output is correct
8	Correct	2 ms	544 KB	Output is correct
9	Correct	3 ms	592 KB	Output is correct
10	Correct	2 ms	592 KB	Output is correct

Subtask #2

7.0 / 7.0

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

Subtask #3

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	872 KB	Output is correct
2	Correct	5 ms	1256 KB	Output is correct
3	Correct	4 ms	1256 KB	Output is correct
4	Correct	4 ms	1276 KB	Output is correct
5	Correct	5 ms	1276 KB	Output is correct
6	Correct	5 ms	1404 KB	Output is correct
7	Correct	4 ms	1532 KB	Output is correct
8	Correct	4 ms	1532 KB	Output is correct
9	Correct	3 ms	1532 KB	Output is correct
10	Correct	3 ms	1532 KB	Output is correct

Subtask #4

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	751 ms	131836 KB	Output is correct
2	Correct	912 ms	132788 KB	Output is correct
3	Correct	605 ms	132788 KB	Output is correct
4	Correct	497 ms	132788 KB	Output is correct
5	Correct	718 ms	146076 KB	Output is correct
6	Correct	681 ms	148184 KB	Output is correct
7	Correct	665 ms	148184 KB	Output is correct
8	Correct	863 ms	148184 KB	Output is correct
9	Correct	964 ms	158360 KB	Output is correct
10	Correct	293 ms	158360 KB	Output is correct

Subtask #5

0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	863 ms	158360 KB	Output is correct
2	Execution timed out	1094 ms	158360 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-