답안 #587392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587392	2022-07-01T18:48:15 Z	GioChkhaidze	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	100 / 100	670 ms	170580 KB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 6;

char C[N];
int Tries, idx, Nowidx, D[N], dep[N], T[N][37], P[N][21];

void Init() {
	Tries = 1;
	Nowidx = 1;
	D[0] = Nowidx;
	dep[Nowidx] = 0;
}

void TypeLetter(char c) {
	++idx;	
	int t = c - 'a';	
	if (!T[Nowidx][t]) {
		T[Nowidx][t] = ++Tries;
		C[Tries] = c;
		dep[T[Nowidx][t]] = dep[Nowidx] + 1;
		P[T[Nowidx][t]][0] = Nowidx;
				
		for (int j = 1; j <= 20; ++j)
			P[T[Nowidx][t]][j] = P[P[T[Nowidx][t]][j - 1]][j - 1];
	}
	D[idx] = T[Nowidx][t];
	Nowidx = D[idx];
}

void UndoCommands(int x) {
	++idx;	
	D[idx] = D[idx - x - 1];
	Nowidx = D[idx];
}

char GetLetter(int x) {
	++x;
	int Nq = Nowidx;
	if (dep[Nq] == x) return C[Nq];
	for (int i = 20; i >= 0; --i) {
		if (dep[P[Nq][i]] > x) Nq = P[Nq][i];
	}
	Nq = P[Nq][0];
	return C[Nq];		
}

Subtask #1

5.0 / 5.0

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

Subtask #2

7.0 / 7.0

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

Subtask #3

22.0 / 22.0

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

Subtask #4

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	382 ms	140200 KB	Output is correct
2	Correct	418 ms	154028 KB	Output is correct
3	Correct	351 ms	150320 KB	Output is correct
4	Correct	360 ms	114944 KB	Output is correct
5	Correct	413 ms	130532 KB	Output is correct
6	Correct	341 ms	166192 KB	Output is correct
7	Correct	430 ms	82276 KB	Output is correct
8	Correct	347 ms	124272 KB	Output is correct
9	Correct	477 ms	170580 KB	Output is correct
10	Correct	269 ms	124744 KB	Output is correct

Subtask #5

40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	548 ms	119884 KB	Output is correct
2	Correct	670 ms	106304 KB	Output is correct
3	Correct	349 ms	114764 KB	Output is correct
4	Correct	400 ms	83908 KB	Output is correct
5	Correct	360 ms	126776 KB	Output is correct
6	Correct	361 ms	118064 KB	Output is correct
7	Correct	374 ms	126360 KB	Output is correct
8	Correct	449 ms	61352 KB	Output is correct
9	Correct	615 ms	110192 KB	Output is correct
10	Correct	241 ms	123888 KB	Output is correct