제출 #576060

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

scrivener

#include<bits/stdc++.h>
using namespace std;

char curr[1000005];
int sparse[1000005][21];
int cntop;
int len[1000005];

void Init() {
	cntop = 0;
}

void TypeLetter(char L) {
	cntop++;
	len[cntop] = len[cntop-1] + 1;
	curr[cntop] = L;
	sparse[cntop][0] = cntop-1;
	for(int i=1; i<=20; i++) {
		if(sparse[cntop][i-1] == 0) sparse[cntop][i-1] = 0;
		else sparse[cntop][i] = sparse[sparse[cntop][i-1]][i-1];
	}
}

void UndoCommands(int U) {
	cntop++;
	len[cntop] = len[cntop-U-1];
	curr[cntop] = curr[cntop-U-1];
	for(int i=0; i<=20; i++) sparse[cntop][i] = sparse[cntop-U-1][i];
}

char GetLetter(int P) {
	P++;
	int ptr = len[cntop], tmp = cntop;
	for(int i=20; i>=0; i--) {
		if(ptr - (1<<i) >= P) {
			ptr -= (1<<i);
			tmp = sparse[tmp][i];
		}
	}
	return curr[tmp];
}

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