제출 #1056832

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1056832		lovrot	크레이피쉬 글쓰는 기계 (IOI12_scrivener)	C++17	100 / 100	187 ms	64528 KiB

scrivener

#include <cstdio>

#define debug(...) //fprintf(stderr, __VA_ARGS__)

using namespace std;

const int LOG = 20;
const int N = 1 << LOG;

char c[N] = {'*'};
int nov = 1, up[N][LOG], dep[N], pos[N], lst;

char climb(int u, int x) { 
	for(int i = LOG - 1; i >= 0; --i) { 
		if(x & (1 << i)) { 
			u = up[u][i];
		}
	}
	return c[u];
}

void Init() {}

void TypeLetter(char L) {
	up[nov][0] = pos[lst];	
	for(int i = 1; i < LOG; ++i) { 
		up[nov][i] = up[up[nov][i -	1]][i - 1]; 
	}

	dep[nov] = dep[pos[lst]] + 1;
	c[nov] = L;
	pos[++lst] = nov++;
}

void UndoCommands(int U) {
	++lst;
	pos[lst] = pos[lst - U - 1];	
}

char GetLetter(int P) {
	return climb(pos[lst], dep[pos[lst]] - P - 1);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40