답안 #60698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
60698	2018-07-24T14:30:59 Z	aome	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	100 / 100	784 ms	144416 KB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;

int cur;
int cnt1, cnt2;
int h[N];
int par[20][N];
int arr[N];
char a[N];

void Init() {}

void TypeLetter(char L) {
	++cnt1;
	par[0][cnt1] = cur, h[cnt1] = h[cur] + 1;
	cur = cnt1, a[cur] = L;
	for (int i = 1; i < 20; ++i) {
		par[i][cur] = par[i - 1][par[i - 1][cur]];
	}
	arr[++cnt2] = cur;
}

void UndoCommands(int U) {
	cur = arr[cnt2 + 1] = arr[cnt2 - U];
	++cnt2;
}

char GetLetter(int P) {
	int pos = cur;
	int H = h[cur] - (P + 1);
	for (int i = 19; i >= 0; --i) {
		if (H >= (1 << i)) {
			H -= (1 << i), pos = par[i][pos];
		}
	}
	return a[pos];
}

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	764 KB	Output is correct
2	Correct	3 ms	788 KB	Output is correct
3	Correct	3 ms	872 KB	Output is correct
4	Correct	3 ms	880 KB	Output is correct
5	Correct	3 ms	884 KB	Output is correct
6	Correct	4 ms	888 KB	Output is correct
7	Correct	3 ms	888 KB	Output is correct
8	Correct	3 ms	912 KB	Output is correct
9	Correct	4 ms	916 KB	Output is correct
10	Correct	3 ms	916 KB	Output is correct

Subtask #3

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1052 KB	Output is correct
2	Correct	4 ms	1064 KB	Output is correct
3	Correct	6 ms	1232 KB	Output is correct
4	Correct	4 ms	1260 KB	Output is correct
5	Correct	4 ms	1264 KB	Output is correct
6	Correct	5 ms	1492 KB	Output is correct
7	Correct	6 ms	1496 KB	Output is correct
8	Correct	4 ms	1496 KB	Output is correct
9	Correct	5 ms	1496 KB	Output is correct
10	Correct	5 ms	1496 KB	Output is correct

Subtask #4

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	494 ms	56116 KB	Output is correct
2	Correct	448 ms	65500 KB	Output is correct
3	Correct	398 ms	69072 KB	Output is correct
4	Correct	395 ms	69072 KB	Output is correct
5	Correct	467 ms	72896 KB	Output is correct
6	Correct	328 ms	90100 KB	Output is correct
7	Correct	406 ms	90100 KB	Output is correct
8	Correct	411 ms	90100 KB	Output is correct
9	Correct	553 ms	106732 KB	Output is correct
10	Correct	357 ms	106732 KB	Output is correct

Subtask #5

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	661 ms	106732 KB	Output is correct
2	Correct	784 ms	106732 KB	Output is correct
3	Correct	429 ms	106732 KB	Output is correct
4	Correct	442 ms	106732 KB	Output is correct
5	Correct	307 ms	121020 KB	Output is correct
6	Correct	331 ms	122772 KB	Output is correct
7	Correct	343 ms	130168 KB	Output is correct
8	Correct	657 ms	130168 KB	Output is correct
9	Correct	773 ms	134636 KB	Output is correct
10	Correct	253 ms	144416 KB	Output is correct