Submission #908458

#	Time	Username	Problem	Language	Result	Execution time	Memory
908458		Blagoj	Crayfish scrivener (IOI12_scrivener)	C++17	0 / 100	238 ms	67928 KiB

scrivener

#include <bits/stdc++.h>

using namespace std;

const int mxn = 1e6 + 10;

int nxt[mxn][21], sz[mxn], cnt = 0;
char c[mxn];

void Init() { }

void TypeLetter(char L) { 
	cnt++;
	c[cnt] = L;
	sz[cnt] = sz[cnt - 1] + 1;
	nxt[cnt][0] = cnt - 1;
	for (int i = 1; i <= 20; i++) nxt[cnt][i] = nxt[nxt[cnt][i - 1]][i - 1];
}

void UndoCommands(int U) {
	cnt++;
	sz[cnt] = sz[cnt - U];
	nxt[cnt][0] = nxt[cnt - U][0];
	c[cnt] = c[cnt - U];
	for (int i = 1; i <= 20; i++) nxt[cnt][i] = nxt[nxt[cnt][i - 1]][i - 1];
}

char GetLetter(int P) { 
	int len = sz[cnt] - P;
	int ans = cnt;
	for (int i = 20; i >= 0; i--) {
		if (len & (1 << i)) ans = nxt[ans][i];
	} 
	return c[ans];
}

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