답안 #43805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43805	2018-03-24T03:41:25 Z	gnoor	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	100 / 100	850 ms	140588 KB

scrivener

#ifdef debug
#include "grader.cpp"
#endif

#include <cstdlib>

struct node {
	char x;
	int pos;
	node* left[21];									
};

node* version[1000100];
int curVer=0;
int curIdx=1;
char last;

void Init() {
	version[0]=new node();
	version[0]->x=0;
	version[0]->pos=-1;
	for (int i=0;i<21;i++) version[0]->left[i]=version[0];	
}

void TypeLetter(char L) {
  //last = L;
	version[curIdx]=new node();
	version[curIdx]->x=L;
	version[curIdx]->pos=version[curVer]->pos+1;
	version[curIdx]->left[0]=version[curVer];
	for (int i=1;i<21;i++) version[curIdx]->left[i]=version[curIdx]->left[i-1]->left[i-1];	
	curVer=curIdx;
	curIdx++;
}

void UndoCommands(int U) {
	//version[curIdx]=new node();
	version[curIdx]=version[curIdx-U-1];
	curVer=curIdx;
	curIdx++;
}

char GetLetter(int P) {
	node* cur=version[curVer];
	int dif=cur->pos-P;
	for (int i=0;i<21;i++) {
		if (dif&(1<<i)) {
			cur=cur->left[i];
		}
	}
	return cur->x;
}

Subtask #1

5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	248 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	620 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	2 ms	620 KB	Output is correct
6	Correct	2 ms	620 KB	Output is correct
7	Correct	1 ms	620 KB	Output is correct
8	Correct	2 ms	620 KB	Output is correct
9	Correct	2 ms	620 KB	Output is correct
10	Correct	2 ms	620 KB	Output is correct

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	2 ms	620 KB	Output is correct
4	Correct	1 ms	620 KB	Output is correct
5	Correct	1 ms	620 KB	Output is correct
6	Correct	1 ms	620 KB	Output is correct
7	Correct	2 ms	620 KB	Output is correct
8	Correct	1 ms	620 KB	Output is correct
9	Correct	1 ms	620 KB	Output is correct
10	Correct	1 ms	620 KB	Output is correct

Subtask #3

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	876 KB	Output is correct
2	Correct	4 ms	876 KB	Output is correct
3	Correct	3 ms	876 KB	Output is correct
4	Correct	3 ms	1132 KB	Output is correct
5	Correct	3 ms	1132 KB	Output is correct
6	Correct	3 ms	1264 KB	Output is correct
7	Correct	3 ms	1264 KB	Output is correct
8	Correct	3 ms	1264 KB	Output is correct
9	Correct	4 ms	1264 KB	Output is correct
10	Correct	3 ms	1264 KB	Output is correct

Subtask #4

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	739 ms	115340 KB	Output is correct
2	Correct	779 ms	127288 KB	Output is correct
3	Correct	508 ms	127288 KB	Output is correct
4	Correct	458 ms	127288 KB	Output is correct
5	Correct	660 ms	127288 KB	Output is correct
6	Correct	646 ms	138028 KB	Output is correct
7	Correct	603 ms	138028 KB	Output is correct
8	Correct	720 ms	138028 KB	Output is correct
9	Correct	850 ms	140588 KB	Output is correct
10	Correct	319 ms	140588 KB	Output is correct

Subtask #5

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	710 ms	140588 KB	Output is correct
2	Correct	781 ms	140588 KB	Output is correct
3	Correct	464 ms	140588 KB	Output is correct
4	Correct	455 ms	140588 KB	Output is correct
5	Correct	574 ms	140588 KB	Output is correct
6	Correct	537 ms	140588 KB	Output is correct
7	Correct	517 ms	140588 KB	Output is correct
8	Correct	694 ms	140588 KB	Output is correct
9	Correct	847 ms	140588 KB	Output is correct
10	Correct	293 ms	140588 KB	Output is correct