제출 #587392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587392		GioChkhaidze	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++14	100 / 100	670 ms	170580 KiB

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 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40